[BOJ 3737] Cycles of Lanes

문제

---

https://www.acmicpc.net/problem/3737

풀이

---

문제의 그래프가 선인장이므로 선인장을 조금만 변형하면 바로 풀리는 문제였다.

코드

---

import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 5)


def dfs(cur, par):
    global idx, ans
    dfsn[cur] = idx
    visit_node[cur] += 1
    parent[cur] = par
    idx += 1

    for nxt in graph[cur]:
        if (nxt == par) | (dfsn[nxt] >= dfsn[cur]):
            continue

        if visit_node[nxt]:
            res = 0
            temp1 = cur
            temp2 = nxt
            while temp1 != parent[nxt]:
                res += 1
                visit_edge[temp1][temp2] += 1
                temp2 = temp1
                temp1 = parent[temp1]
            ans = max(ans, res)
        else:
            visit_edge[cur][nxt] += 1
            dfs(nxt, cur)


for _ in range(int(sys.stdin.readline())):
    n, m = map(int, sys.stdin.readline().split())

    graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)

    dfsn = [0] * (n + 1)
    visit_node = [0] * (n + 1)
    visit_edge = [defaultdict(int) for _ in range(n + 1)]
    parent = [0] * (n + 1)
    idx = 1
    ans = 0

    dfs(1, -1)

    print(ans)