단순히 한 방향으로 인접해있는 정점들에 대해 방문 여부만 확인하면 되는 게 아니라, 모든 점과 연결되는지를 확인해야 했다. 처음에는 모든 간선들의 방향을 뒤집으면 될까 싶었는데 진입 및 진출 차수를 모두 확인해야 할 것 같아서 아예 두 개의 인접 리스트를 만들고자 했다.
def count_visited(arr, start):
visited = [0] * (N + 1)
stack = [start]
while stack:
now = stack.pop()
for nxt in arr[now]:
if not visited[nxt]:
visited[nxt] = 1
stack.append(nxt)
return visited.count(1)
T = int(input())
for tc in range(1, T+1):
N = int(input())
M = int(input())
cnt = 0
adj_out = [[] for _ in range(N + 1)]
adj_in = [[] for _ in range(N + 1)]
for _ in range(M):
a, b = map(int, input().split())
adj_out[a].append(b)
adj_in[b].append(a)
for student in range(1, N + 1):
if count_visited(adj_out, student) + count_visited(adj_in, student) == N - 1:
cnt += 1
print('#{} {}'.format(tc, cnt))
인접 정점을 카운트 할 수 있는 함수를 따로 작성했고, 모든 정점에 대해서 in & out 인접 리스트의 리턴값을 확인한 뒤 이 값이 정점의 개수와 같다면 결과를 +1 해주는 식으로 풀이했다.