[BOJ 2111] 선인장

문제

---

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

풀이

---

선인장이란 연결된 무향 그래프의 일종으로, 모든 간선이 최대 한 개의 사이클에만 속할 수 있는 그래프이다.

Cactus? Not cactus?에서 나온 선인장의 정의와는 약간 다르다.

이전 정의가 노드에 관한 것이었다면 이번 정의는 엣지에 관한 것이다.

이 정의가 조금 더 통용되는 것 같다.

새로운 선인장의 정의를 기준으로 그래프가 선인장인지 아닌지 판별하려면 약간의 조작만 거치면 된다.

visit_node 배열과 visit_edge 배열을 따로 만들어 dfs 시 몇 번 지나갔는지 카운팅 해준다.

그러다가 2번 이상 카운팅 된 엣지가 발견될 시 선인장이 아니라는 결론을 내릴 수 있다.

추가로 서브그래프의 개수를 리턴해야 되는데, 이는 $ \prod $ (사이클을 이루는 엣지의 개수 + 1)임을 쉽게 알 수 있다.

코드

---

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

n, m = map(int, sys.stdin.readline().split())

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


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 = 1
            temp1 = cur
            temp2 = nxt
            while temp1 != parent[nxt]:
                res += 1
                if visit_edge[temp1][temp2] == 2:
                    print(0)
                    exit()

                visit_edge[temp1][temp2] += 1
                temp2 = temp1
                temp1 = parent[temp1]
            ans *= res
        else:
            visit_edge[cur][nxt] += 1
            dfs(nxt, cur)


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 = 1

dfs(1, -1)

dfsn[0] = 1
if 0 in dfsn:
    print(0)
else:
    print(ans)

노드가 2만 개, 간선이 4만 개 일 때도 들어올 수 있어서 pypy3은 MLE가 뜬다.

python3는 스무스하게 통과하는데, 난이도 기여를 보니 다른 언어들은 큰 수 연산을 하는 데 어려움이 있었다고 한다.