[BOJ 1170] 선인장의 개수

문제

---

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

풀이

---

Cactus? Not cactus?를 풀고 나니 굉장히 쉽게 느껴졌던 문제다.

위 문제와는 다르게 연결 그래프가 아니라서 각 연결 요소 별로 선인장인지 아닌지 판별해 주면 된다.

N의 범위가 200 이하인데 왜 시간제한이 2초나 되는지 모르겠다.

코드

---

import sys

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)


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

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

        if visit[nxt]:
            if flag:
                temp = cur
                while temp != parent[nxt]:
                    if visit[temp] == 2:
                        flag = 0

                    visit[temp] += 1
                    temp = parent[temp]
            
        else:
            dfs(nxt, cur)


dfsn = [0] * (n + 1)
visit = [0] * (n + 1)
parent = [0] * (n + 1)
idx = 1
ans = 0

for i in range(1, n + 1):
    if not visit[i]:
        flag = 1
        dfs(i, -1)
        ans += flag

print(ans)