import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
def DFS(now,sign):
global gameover
if gameover:
return
visited[now] = sign
for next in graph[now]:
if visited[next]==sign:
gameover = 1
if not visited[next]:
DFS(next,-sign)
N,M = map(int,input().split())
graph = [[] for i in range(N+1)]
for _ in range(M):
x,y = map(int,input().split())
graph[x].append(y); graph[y].append(x)
visited = [0]*(N+1)
gameover = 0
DFS(1,1)
print(0 if gameover else visited.count(-1)*visited.count(1)*2)
간단한 DFS 문제
풀이는 금방 생각났는데 이상한 곳에서 헤맸던 문제였다.
그래프에서 홀수번째 노드와 짝수번째 노드를 구분할 수 있는지에 대한 문제이다. 홀수번째 노드와 짝수번째 노드가 구분되면, 각각 홀수, 짝수번 노드에 사자와 토끼가 위치하는 경우 영원히 둘은 만날 수 없게된다. 이를 이용하는 문제이다.
풀이를 설명하면,
1. DFS로 탐색한다.
2. 현재 부호가 1이면 visited에 1로 기록하고, -1이면 -1로 기록한다.
3. 현재 부호가 1인데 다음 노드가 이미 방문된 상태고, 부호가 현재 부호와 같다면, 홀수 짝수 노드를 구분할 수 없으므로 0을 출력한다.
4. 3에 해당하지 않는 경우 1로 기록된 노드의 수 * -1로 기록된 노드의 수 * 2를 출력한다 (2를 곱하는 이유는 사자가 홀수노드일 때와 토끼가 홀수 노드일 때 두가지가 있으므로)
헤맸던 이유는 홀수 노드의 수와 짝수 노드의 수가 당연히 각각 N/2 또는 N/2+1이라고 착각했었다. 그런데 다시 생각해보니 그렇지 않다는 것을 알게 되었다.
오늘의 교훈) 홀수 노드와 짝수 노드의 수는 정확히 절반이 아니다