백준 28102 단순한 그래프와 이상한 쿼리 풀이

문제

28102번: 단순한 그래프와 이상한 쿼리 (acmicpc.net)

28102번: 단순한 그래프와 이상한 쿼리

 

풀이

모든 간선의 가중치가 1이고, 중복방문을 허용한다.

어떤 경로의 길이가 X라하자. 가장 간단한 중복방문은 간선하나를 왔다갔다하는 것이다. 중복방문이 발생할때마다 경로의 길이가 2 늘어난다.

만약 X가 짝수라면 중복방문이 가능하므로 X 이상의 모든 짝수 길이로 방문 가능하다.

마찬가지로 홀수라면 X 이상의 모든 홀수 길이로 방문 가능하다.

짝수길이로 방문 가능하다면, 쿼리의 모든 k에 대해 쿼리가 성립한다.

k가 홀수여도 짝수배를 해주면 짝수가 된다. k가 작아도 k에 큰 수를 곱해주면된다. k가 매우커도 중복방문을 하다보면 만족할 것이다.

홀수길이로 방문 가능하다면, k가 홀수일 때만 성립한다. 홀수 * 홀수 = 홀수인 경우만 있기 때문이다.

 

모든 정점쌍에 대해 홀수길이 경로가 존재하는지, 짝수길이 경로가 존재하는지 계산하는건 비효율적이다.

우리들은 각 컴포넌트에 대해 그래프 탐색을 1번만 수행한다면 우리가 필요한 것을 다 알 수 있다.

필요한건 다음과 같다.

compo = [-1] * (N + 1) 
'''
compo[n]은 n이 무슨 컴포넌트에 속하는지 알려준다. 
-1은 정의안된 상태이다. 탐색 시작점으로 값을 채워주면 된다.
'''
visit = [[False,False] for _ in range(N + 1)] 
'''
visit[n][0]가 True라면 컴포넌트 시작점과 n의 경로 중 짝수길이 경로가 있는 것이다.
visit[n][1]이 False라면 컴포넌트 시작점과 n의 경로 중 홀수길이 경로가 있는 것이다.
'''

각 정점을들 순회하며 compo[정점] 이 -1이라면 BFS를 시작한다.(편한 탐색법을 사용하자.)

visit[정점][0] = True이다. 거리가 0이라면 짝수이기 때문이다.

탐색을 해서 visit을 채워준다.

    compo[s] = s
    visit[s][0] = True
    q = deque([s])
    while q:
        node = q.popleft()
        for n in g[node]:
            compo[n] = s
            if visit[node][0]:
                if not visit[n][1]:
                    visit[n][1] = True
                    q.append(n)
            if visit[node][1]:
                if not visit[n][0]:
                    visit[n][0] = True
                    q.append(n)

 

 

쿼리는 a,b,k가 주어진다.

만약 a,b가 다른 컴포넌트라면 No를 출력하고 볼 필요도 없다.

a,b가 속한 컴포넌트의 탐색 시작점을 c라고하자,visit은 c->a,c->b에 대한 정보를 담고 있다.

무향그래프이므로 a <--> b = a <--> c <--> b 로 해석 가능하다. (<-->는 경로를 나타낸다.)

짝수 + 홀수 = 홀수이고, 짝수 + 짝수 (or 홀수 + 홀수) = 짝수이다.

따라서 (visit[a][0] 와 visit[b][0]가 둘다 True) or (visit[a][1] 과 visit[b][1]이 둘다 True)라면 모든 k에 대해 Yes이다.

나머지 경우엔 경로의 길이가 홀수이다. k가 홀수일 때만 Yes를 출력한다.