import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
def DFS(now):
global id
visited[now] = nowid = id
stack.append(now)
for next in graph[now]:
if not visited[next]:
id += 1
DFS(next)
visited[now] = min(visited[now],visited[next])
if visited[now] == nowid:
n = len(scc); scc.append([])
while 1:
x = stack.pop()
visited[x] = 1e7
scc[-1].append(x); sccnum[x] = n
if x==now:
break
for _ in range(int(input())):
N,M = map(int,input().split())
graph = [[] for i in range(N)]
for _ in range(M):
a,b = map(int,input().split())
graph[a].append(b)
stack = []; scc = []; visited = [0]*N; sccnum = [0]*N
for i in range(N):
if not visited[i]:
id = 1
DFS(i)
C = len(scc); indegree = [0]*C
for i in range(N):
for j in graph[i]:
if sccnum[i]!=sccnum[j]:
indegree[sccnum[j]] += 1
print(*sorted(scc[indegree.index(0)]) if indegree.count(0)==1 else ["Confused"],sep="\n")
print(); input()
SCC+위상정렬 문제이다.
도미노 [백준 4196번] 도미노 (Python3) (tistory.com) 문제와 거의 유사하다.
도미노 문제가 indegree가 0인 SCC의 개수를 세어주는 문제였다면, 이 문제는 indegree가 0인 SCC가 1개이면 해당 SCC의 요소를 출력하고, SCC가 1개보다 많으면 Confused를 출력해주면 된다.
오늘의 교훈) SCC를 잘 활용하자