가톨릭대학교 학생인 쿠기는 졸업을 앞두고 여행을 가기로 결심했다. 꼼꼼한 성격인 쿠기는 여행을 가기 전에 여행계획을 미리 세우려 한다.
우선 쿠기는 가고 싶은 관광지를 모두 골라 여행지도를 그려봤다. 여행지도는 1부터 N까지의 서로 다른 번호를 가진 N개의 관광지가 있으며, 서로 다른 두 관광지를 오갈 수 있는 M개의 길들로 이루어져 있다. 이때, 모든 관광지는 여러 번 방문이 가능하다.
쿠기는 여행예산이 이미 정해져 있기 때문에 아쉽지만 여행지도에서 관광지를 하나씩 제외해보며 여행계획을 세우려 한다. 만약, 어떤 관광지를 제외했다면, 제외한 관광지와 연결된 모든 길도 여행지도상에서 제외가 된다. 또한, 제외된 관광지와 길은 여행지도에서 영구적으로 제외가 된다.
쿠기가 생각하는 이상적인 여행계획은 여행지도에 반드시 하나 이상의 관광지가 존재하고 임의의 관광지에서 다른 어떤 관광지도 모두 도달할 수 있어야 한다. 쿠기를 도와 여행지도에서 관광지를 계속해서 하나씩 제외했을 때 이상적인 여행계획이 되는지 확인해보자.
이 노드와 연결된 엣지들을 union-find를 통하여 합친 후, 그 결과인 그래프가 1개로 이루어지는지 검사
로 거의 동일하다. 여기서 그래프의 루트 노드들을 저장해두고, 노드를 하나 추가하였을 때 루트 노드들의 개수를 갱신하여 세면 그래프의 개수를 셀 수 있다. 만약 노드의 추가로 인하여 둘 이상의 그래프가 연결되었다면 루트 노드가 하나로 통합될 것이고, 노드가 연결되지 않은 채 그대로라면 루트 노드가 하나 늘어나는 효과를 가질 것이다. 총 시간복잡도는 O(N+M)이 된다. (엣지를 최대 2M번 확인하게 되고, 이 엣지 확인 연산이 N번 이루어지게 된다)
풀이 코드
from collections import defaultdict
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
parents = list(range(N+1))
edge_dict = defaultdict(list)
for _ in range(M) :
a, b = map(int, input().split())
edge_dict[a].append(b)
edge_dict[b].append(a)
visited = [False] * (N+1)
graph = set()
connect_queue = [int(input()) for _ in range(N)]
def find(a) :
if parents[a] == a :
return a
parents[a] = find(parents[a])
return parents[a]
def union(a, b) :
pa, pb = find(a), find(b)
if pa > pb :
pa, pb = pb, pa
parents[pb] = pa
return
def is_full_connected(n) :
global graph
visited[n] = True
graph.add(n)
for m in edge_dict[n] :
if visited[m] :
union(m, n)
graph = { find(g) for g in graph }
return len(graph) == 1
ans = ["DISCONNECT"]
for n in reversed(connect_queue) :
res = "CONNECT" if is_full_connected(n) else "DISCONNECT"
ans.append(res)
print(*reversed(ans), sep='\n')