1. 단절점이란?

하나의 컴포넌트(connected component)로 구성되어 있는 그래프에서 특정 정점을 제거할 때, 컴포넌트의 개수가 증가하는 정점을 단절점 이라고 한다.

2. 단절점 구하는 법

DFS 트리를 이용하면 단절점을 빠르게 구할 수 있다.

(DFS 트리: 임의의 그래프에서 DFS를 돌면서 방문 순서대로 노드의 번호를 매기며 생성되는 트리)

DFS 트리에서 단절점의 판별볍은 다음과 같다.

1. 어떤 정점 $v$가 dfs tree상에서 root이고, 자식의 개수가 $2$ 이상이면 단절점이다.
2. 어떤 정점 $v$가 dfs tree상에서 root이고, 자식의 개수가 $1$ 이하라면 단절점이 아니다.
3. 어떤 정점 $v$가 dfs tree상에서 root가 아니고, $v$의 자손 정점 중 $v$를 거치지 않고 $v$이전에 방문했던 정점에 갈 수 있다면 단절점이 아니다.

현재 정점보다 먼저 방문했던 정점에 갈 수 있는지 확인하는 것은 Tarjan’s Algorithm을 사용하면 된다.

3. 코드

int n, m;
vector<int> adj[10'001];
int ord[10'001];
int idx = 1;

bool isCut[10'001];

int dfs(int cur)
{
    ord[cur] = idx++;

    int ret = ord[cur];
    int ccnt = 0;

    for(int nxt: adj[cur]){
        if(ord[nxt]){
            ret = min(ret, ord[nxt]);
            continue;
        }
        else{
            int low = dfs(nxt);
            ret = min(ret, low);
            ccnt++;
            
            if(ord[cur] != 1 && ord[cur]<=low) isCut[cur] = true;
        }
    }
    if(ord[cur] == 1 && ccnt>=2) isCut[cur] = true;

    return ret;
}