import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
def DFS(now,last):
global id
visited[now] = ID[now] = id
cnt = 0; check = 0
for next in graph[now]:
if next==last:
continue
if visited[next]:
visited[now] = min(visited[now],ID[next])
else:
cnt += 1; id += 1
DFS(next,now)
if visited[next] >= ID[now]:
check = 1
visited[now] = min(visited[now],visited[next])
if ID[now]!=1 and check or ID[now]==1 and cnt>1:
point.append(now)
N,M = map(int,input().split())
graph = [[] for i in range(N+1)]
for _ in range(M):
a,b = map(int,input().split())
graph[a].append(b)
graph[b].append(a)
visited = [0]*(N+1); ID = [0]*(N+1)
point = []
for i in range(1,N+1):
if not visited[i]:
id = 1
DFS(i,i)
print(len(point))
if point:
print(*sorted(point))단절점 알고리즘 기본문제이다.
알고리즘에 대한 설명은 https://www.crocus.co.kr/1164 여기를 참고하였다.
알고리즘에 대한 설명을 읽고 SCC와 별 다를게 없다고 생각했다. 그래서 쉽게 코드를 짰는데 계속해서 실수가 나왔다. 그러다 보니 무려 13번이나 틀렸습니다! 끝에 겨우겨우 맞출 수 있었다.
정확하게 이해를 하지 않고 문제를 풀게 되면 구현과정에서 여러가지 실수가 나올 수 있는 문제이다.
일단 내가 한 실수를 정리하면,
1. 출력초과의 경우 단절점이 없는 경우에 한줄 더 출력해서 발생하였다. 단절점이 없을때는 0 한줄만을 출력해야한다.
2. 현재 노드가 이전에 탐색한 노드로 갈 수 있는지가 아니라 현재 노드의 "자식"이 이전에 탐색한 노드로 갈 수 있는지를 확인해야 한다.
3. 현재 노드의 자식이 2개 이상이더라도 루트노드가 아니라면 단절점이 아닐 수 있다. 조건문을 명확하게 명시하자.
4. visited를 갱신할 때, visited[next]로 갱신해선 안된다. 자식노드의 경우 visited로 갱신하고, 이미 탐색한 노드라면 ID로 갱신해야한다. (참고 https://www.acmicpc.net/board/view/34811)
5. 내가 실수한 부분은 아니지만 주어진 그래프가 연결그래프가 아닐 수 있음에 주의하자
오늘의 교훈) 단절선을 풀어보자