백준 4191번
https://www.acmicpc.net/problem/4191

문제

후기

⏰ 풀이시간 15분 ++⏰

맞힌 사람이 많지 않은 그래프 문제를 풀기 위해 풀은 사람이 적은 순으로 정렬해서

찾은 문제의 4번째다. 문제의 결론을 이야기 하자면,

테스트 케이스 마다 그래프와 어떠한 정점이 주어지는데,
그 정점 도미노가 나머지 도미노를 몇개나 무너뜨리냐에 대한 문제다.

해당 정점에서 시작된 DFS가 몇개의 정점을 방문하면 되는지에 대해 출력해주면 된다.

기초적인 문제라 주석은 생략했다.

나의 풀이

import sys
input= sys.stdin.readline
sys.setrecursionlimit(10**7)

def dfs(v):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(i)
            visited[i] = True

T = int(input())
for _ in range(T):
    N , M , L = map(int,input().split())
    graph = [ [] for _ in range(N+1)]
    visited= [False] * (N+1)
    li = []
    for _ in range(M):
        a,b = map(int,input().split())
        graph[a].append(b)
    
    for _ in range(L):
        li.append(int(input()))
    
    for i in li:
        dfs(i)
    print(visited.count(True))