단절점과 단절선

개요

단절점과 단절선은 무방향 그래프에서 각각의 정점 또는 간선을 제거했을 때, 그래프가 나눠지게 만드는 정점(단절점) 및 간선(단절선)을 의미합니다. 단절점과 단절선은 모든 정점에서 DFS를 진행하면 구할 수 있지만, 단 1번의 DFS 탐색으로 모든 단절점과 단절선을 구할 수 있습니다. 그리고 이 개념은 방향 그래프에서 SCC를 나눌 때에도 사용할 수 있습니다.

 

단절점 구하기

단절점을 구하기 위해서는 DFS 탐색 트리를 만들어야 합니다. DFS 탐색 트리를 만들어서 정점에 방문한 순서대로 번호를 매기고, 각각의 정점에서 갈 수 있는 가장 낮은 위치를 찾는 알고리즘을 사용합니다. 여기서 말하는 가장 낮은 위치란 트리에서 높이가 낮은 정점을 의미하며, 우리는 방문 순서에 따라 트리를 만들고 있기에 방문 순서가 가장 빠른 정점을 의미합니다. 따라서, 우리는 현재 탐색한 정점과 연결된 정점들이 갈 수 있는 방문 순서가 가장 빠른 정점을 찾으면 됩니다. 만약, 주변의 모든 정점에서 갈 수 있는 방문 순서가 가장 빠른 정점이 지금 탐색하는 현재 정점이라면 지금 정점이 바로 단절점이 됩니다. 이는 주변의 모든 정점은 현재 정점보다 높은 정점과 연결된 역간선이 없다는 의미이며, 현재 정점을 지운다면 그래프는 나누어지게 됩니다.

 

다만, 예외상황이 하나 있는데 바로 루트에서 연결된 정점이 딱 1개인 경우입니다. 이 경우, 위의 알고리즘을 그대로 사용하면 루트 정점을 단절점으로 판단하지만 문제는 연결된 정점이 1개이기 때문에 루트 노드를 제거할 경우, 그래프가 나누어지지 않습니다. 따라서, 현재 정점이 루트 노드라면 자식 노드의 개수가 2개인지 확인하는 과정이 따로 필요합니다.

 

소스코드

소스코드는 11266. 단절점(https://www.acmicpc.net/problem/11266) 기준입니다.

#include <stdio.h>
#include <string.h>
#include <set>
#include <vector>
#include <algorithm>
#define NMAX 10010
using namespace std;
 
int v, e;
int a, b, cnt;
 
int visit[NMAX];
 
set<int> ans;
vector< vector< int > > adj(NMAX);
 
int searchCut(int node, int isRoot) {
    int ret, subtree, child=0;
    
    // 방문 순서 기록 & 반환값 초기화
    visit[node] = cnt++;
    ret = visit[node];
    
    for(auto nxt:adj[node]) {
        // 방문한 노드는 방문 순서만 확인
        if(visit[nxt] >= 0) ret = min(ret, visit[nxt]);
        
        // 방문하지 않은 노드는 역방향 값 탐색
        else {
            // 루트인 경우, 자식 노드의 개수가 필요함
            child++;
            
            // 자식 노드의 역방향 간선 확인하기
            // 역방향 간선이 부모 노드를 넘지 못 하면 지금 노드는 단절점
            subtree = searchCut(nxt, 0);
            if(!isRoot and subtree >= visit[node]) ans.insert(node);
            
            // 역방향 간선으로 갈 수 있는 최댓값 저장
            ret = min(ret, subtree);
        }
    }
    
    if(isRoot and child>=2) ans.insert(node);
    
    return ret;
}
 
int main() {
    // input
    scanf("%d %d", &v, &e);
    for(int i=1;i<=e;i++) {
        scanf("%d %d", &a, &b);
        
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    memset(visit, -1, sizeof(visit));
    
    // DFS
    for(int i=1;i<=v;i++) {
        if(visit[i] == -1) searchCut(i, 1);
    }
    
    // Print
    printf("%d\n", ans.size());
    for(auto t:ans) printf("%d ", t);
}

 

단절선 구하기

단절선 역시 단절점을 구하는 방식과 동일하게 진행합니다. 다만, 단절점을 구할 때에는 루트 정점인지 아닌지에 따라 다르게 판단했지만 단절선인 경우에는 한 번에 구할 수 있습니다. 기본 아이디어는 단절선은 항상 트리 간선이라는 점입니다. 따라서, 현재 정점의 자식 노드 중 어떤 정점이 지금 현재 정점을 단절점으로 판단한다면, { 현재 정점, 해당 자식 노드 } 간선이 바로 단절선이 됩니다.

 

소스코드

소스코드는 11400. 단절선(https://www.acmicpc.net/problem/11400) 기준입니다.

#include <stdio.h>
#include <utility>
#include <vector>
#include <set>
#define NMAX 100010
#define VMAX 1000010
using namespace std;
typedef pair<int, int> PAIR;
 
int V, E, a, b;
vector< int > adj[NMAX];
 
int num;
int visited[VMAX], low[VMAX], parent[VMAX];
set< PAIR > ans;
 
void dfs(int idx) {
    
    // low: 가장 높은 역간선 / visited: 방문 순서
    low[idx] = num++;
    visited[idx] = num;
    
    for(int chd:adj[idx]) {
        if(chd == parent[idx]) continue;
        
        if(!visited[chd]) {
            parent[chd] = idx;
            
            dfs(chd);
            
            // idx가 단절점인 경우 >> idx-chd가 단절선
            if(low[chd] >= visited[idx]) {
                if(idx < chd) ans.insert({idx, chd});
                else ans.insert({chd, idx});
            }
        }
        
        // 역간선 구하기
        low[idx] = min( low[idx], low[chd] );
        
    }
}
 
int main() {
    // 입력
    scanf("%d %d", &V, &E);
    for(int i=1;i<=E;i++) {
        scanf("%d %d", &a, &b);
        
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    // 단절선 탐색
    dfs(1);
    
    // 출력
    printf("%d\n", (int)ans.size());
    for(PAIR val:ans) printf("%d %d\n", val.first, val.second);
}
 

참고

https://justicehui.github.io/hard-algorithm/2019/01/06/ArticulationPoint/

[그래프] 단절점

https://m.blog.naver.com/kks227/220802704686

이중 연결 요소(Biconnected Component) (수정: 2019-02-13)