[BOJ] Cactus? Not cactus? (no.10891)

문제

선인장이란 양방향 그래프의 일종인데, 각 정점에 대해 자기 자신으로 돌아오는 경로(단순 사이클)가 하나 이하인 그래프이다. 주어진 그래프가 선인장일까? 아닐까?

입력

첫 번째 줄에 그래프의 정점의 개수와 간선의 개수를 나타내는 두 정수 N,M (1 ≤ N,M ≤ 100,000) 이 공백으로 구분되어 주어진다.

다음 M개의 줄에는 간선이 연결하고 있는 두 정점을 나타내는 두 정수 x,y (1 ≤ x,y ≤ N,x ≠ y)가 공백으로 구분되어 주어진다. 주어진 간선은 중복되지 않으며, 임의의 두 정점에 대해 경로가 존재한다.

출력

주어진 그래프가 선인장이면 "Cactus" 를 아니라면 "Not cactus" 를 출력한다.

🤔 생각

Cactus graph 설명

• 그래프 단절점 개념 공부하는 겸 풀었는데...

• 지금 내 힘만으로 풀 수 있는 문제는 아니었던 것 같다ㅜ

• 사이클 갯수를 세어주되, 리턴할 땐 백엣지로 들어오는 그래프를 하나씩 빼서 리턴해주는 식으로 구현한 코드다. (정점마다 자기 사이클 갯수를 보존하게 하기 위함)

📌 내 풀이

!!!파이썬으로 풀면 메모리 초과 난다!!
C++로 바꿔서 제출해야 한다

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def dfs(cv, pv):
    global ans
    cycle = 0
    offset = 0

    for nv in graph[cv]:
        if nv == pv: continue
        if dist[nv] == 0:
            dist[nv] = dist[cv] + 1
            cycle += dfs(nv, cv)
        elif dist[nv] < dist[cv]: cycle += 1
        elif dist[nv] > dist[cv]: offset += 1
    
    if cycle > 1: 
        print("Not cactus")
        sys.exit()
    return cycle - offset


n,m = map(int, input().split())
graph = [[] for _ in range(n)]
dist = [0]*n
cnt = [0]*n
ans = 0

for _ in range(m):
    a,b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

dist[0] = 1
dfs(0,-1)

print("Cactus")