[n9372] 상근이의 여행 in python

 

---

dfs로 풀었던 문제!

모든 관광지가 연결되어 있으므로

양방향 그래프를 그려준다.

 

양방향 그래프를 구현하는 건

아래와 같이 구현해주면 된다.

a와 b가 양방향으로 연결되어 있다는걸 구현하고자 한다면,

a 인덱스에 b값을 넣고

b 인덱스에 a값을 넣어주면 된다.

 

 for _ in range(m):
        a, b = map(int, input().split())
        # 양방향 그래프
        array[a].append(b)
        array[b].append(a)

 

함수 fs 부분에서는 idx와 ans를 인자로 넘겨준다.

이때 visited 배열도 사용해서

방문했는지 체크한다.

 

만약 방문한 곳이 아니라면 dfs 호출!

방문한 곳이라면 아무런 작업 x

 

 

 

import sys
input=sys.stdin.readline

t = int(input())

def dfs(idx, ans):
    visited[idx] = 1
    for temp in array[idx]:
        if not visited[temp]:
            ans = dfs(temp, ans + 1)
    return ans

for _ in range(t):
    n, m = map(int, input().split())
    array = [[] for _ in range(n + 1)]
    for _ in range(m):
        a, b = map(int, input().split())
        # 양방향 그래프
        array[a].append(b)
        array[b].append(a)
    visited = [0] * (n + 1)
    print(dfs(1, 0))