[SWEA] 최장 경로

[SWEA] 최장 경로

Problem URL : 최장 경로

import sys
sys.stdin = open("input.txt", "r")


def dfs(v, cnt):
    global ans
    if cnt > ans:
        ans = cnt

    for node in adj[v]:
        if not visited[node]:
            visited[node] = 1
            dfs(node, cnt+1)
            visited[node] = 0


T = int(input())
for tc in range(1, T+1):
    N, M = map(int, input().split())

    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        x, y = map(int, input().split())
        adj[x].append(y)
        adj[y].append(x)

    ans = 0
    visited = [0] * (N+1)
    for node in range(1, N+1):  # 모든 경로에서 시작해보아야 한다.
        visited[node] = 1
        dfs(node, 1)
        visited[node] = 0


    print('#{} {}'.format(tc, ans))

Comments

간단한 DFS 문제
주의해야할 점이 있다면 모든 경로에서 시작해서 체크해봐야 한다는 것이다.