정의

절단점 : 그래프의 정점 중에 정점을 제거 했을 때(간선도 포함하여 제거됨) 그래프가 연결되지 않도록 만드는 정점
다리 : 절단점이 정점이라면 그래프가 연결되지 않도록 하는 간선

이론

DFS 1번이면 모든 절단점과 다리를 구할 수 있다. O(V+E)

dfs_num(몇번째 방문인지), dfs_low(도달 가능한 최소의 dfs_num값) 값을 유지해 나간다.
dfs_low(v) >= dfs_num(u) 이면, 정점 u는 절단점이다.
dfs_low(v)가 dfs_num(u)보다 작지 않다는 것으로 유추할 수 있다.

u->v->w 일때, 정점w로 도달할 수 있는 역방향 간선이 존재하지 않는 다는 뜻.
역방향 간선이 존재하지 않으면 해당 정점을 끊으면 그래프도 끊김.
(단, 루트가 절단점이 되려면 자식 2개 이상 가지고 있어야 함.)

절단 다리는 dfs_low(v) > dfs_num(u) 로 “=” 부호만 빠지면 된다. (=부호는 양방향일때 의미).
-> 절단점에서 dfs_low(v) == dfs_num(u) 인 경우에 back edge의 도착점일 때, 그 점(dfs_low인 점)은 절단점이 될 수 있다.

소스 코드

void articulationPointAndBridge(int u){
    dfs_low[u] = dfs_num[u] = dfsNumberCounter++; // 처음에는 두개의 값이 동일하게 세팅됨.
    for (int j = 0; j < AdjList[u].size(); ++j){
        int v = AdjList[u][j];
        if (dfs_num[v] == UNVISITED) { // 트리 간선
            dfs_parent[v] = u;
            if (u == dfsRoot) rootChildren++;
            
            articulationPointAndBridge(v);
            
            if (dfs_low[v] >= dfs_num[u]) // 절단점
                articulation_vertex[u] = true;
            if (dfs_low[v] > dfs_num[u])  // 절단 다리
                printf("edge(%d-%d) is bridge", u, v);
            
            dfs_low[u] = min(dfs_low[u], dfs_low[v]); // dfs_low[u] 갱신
        }
        else if (v != dfs_parent[u]) // 역방향 간선이며, 양방향이 아니라면, (u(parent[u])->v(u)->u(v))
            dfs_low[u] = min(dfs_low[u], dfs_num[v]);
    }
}