[DFS] 그래프 단절점, 단절선

 그래프의 단절점과 단절선이란?

•  단절점: 단절점이란 그 정점을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 정점을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 정점을 말한다.
•  단절선: 단절선이란 그 간선을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 간선을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 간선을 말한다.

 그럼 어떤게 단절점과 단절선을 빠르게 구할 수 있을까? 그래프 탐색 방법은 DFS를 이용하고, 현재의 정점(노드) 또는 간선을 제거했을 때 현재 정점의 하위에서 현재 정점보다 상위 노드로 접근이 가능하냐를 기준으로 단절점/단절선을 구분하는 방법을 사용한다. (그래프는 tree구조가 아니기 때문에 여기에서의 하위/상위 노드는 root에서 시작하는 방문 순서를 의미한다. 즉 상위노드는 root에서 방문순서가 빠른 노드, 하위노드는 root에서 방문순서가 느린 노드를 말한다.)  O(n) 만에 탐색이 가능하다. 

• 단절점: 단절점을 제거할 경우는 정점에 속한 모든 간선이 제거된다. 2가지 기준으로 판별한다. root(임의로 설정)에서 부터 시작해서 정점을 dfs로 탐색하면서 방문 순서를 기록한다. 현재의 노드를 기준으로 하위 노드로 dfs 탐색 결과 가장 빠른 방문 순서를 return할 수 있도록 재귀식을 작성하고, 방문 순서 탐색 결과가 현재의 노드보다 빠르면 단절점이 아니고, 같거나 느리면 단절점이다. 그런데, 더이상 상위 노드가 없는 root는 어떻게 판단할까? root의 경우는 dfs로 탐색하는 자식 노드가 2개 이상이면 단절점으로 판단한다.
• 단절선: 단절점과 다르게 단절선은 해당 edge만 제거되며, 위의 root를 따로 고려해야 하는 것이 필요없다. 다만 단절점과는 다르게 현재 노드를 기준으로 하위 노드를 dfs탐색할 때 현재의 노드로의 탐색을 하지 못하게 만드는 것이 필요하다. 그 후 탐색 결과가 현재의 노드보다 클 경우만 단절선으로 판단한다. (노드의 경우는 현재 노드를 탐색해서 돌아와도 노드 자체를 제거해 버리기 때문에 많은 간선이 들어와도 같은 의미를 가지지만, 간선의 경우는 해당 간선만 제외되기 때문에 현재노드로 가는 간선이 1개 이상인지 판단이 중요하기 때문이다. )

아래 노트를 참고하기 바란다. 

이에 해당하는 문제를 풀어보자.

단절점 문제: 백준 11266

소스코드 

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>

using namespace std;
#define fastio cin.tie(0)->sync_with_stdio(0)
using ll = long long;
using matrix = vector<vector<ll>>;
using vi = vector<int>;
using pii = pair<int, int>;
using vpi = vector<pii>;

bool cmp(pii &a, pii &b) {
    if (a.first == b.first) return a.second <= b.second;
    return a.first < b.first;
}

int v, e;
vi graph[100'010];
int visitno[100'010];
vpi ans;
int cnt;

int dfs(int x, int parent) {
    visitno[x] = ++cnt;
    int ret = visitno[x];

    for(auto next:graph[x]) {
        if(next==parent) continue; 
        if(visitno[next]) ret = min(ret, visitno[next]);
        else {
            int minv = dfs(next, x);
            if(minv > visitno[x]) {
                ans.push_back({min(x, next), max(x, next)});
            }
            ret = min(ret, minv);
        }
    }
    return ret;
}


int main() {
    fastio;
    cin >> v >> e;
    int a, b;
    for(int i=0;i<e;++i) {
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(int i=1; i<=v;++i) if(!visitno[i]) {
        dfs(i, 0);
    }
    
    // vpi의 원소 내부 즉, pii의 순서를 변경할 수는 없다. 그렇다면 이중 for문을 써야겠지요.
    // 자래의 sort는 첫번째 두번째 순서에 맞게 정렬할 뿐이지 첫번째와 두번째를 바꿔주는 것은 아니다. 
    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for(auto &e:ans) {
        cout << e.first << ' ' << e.second << '\n';
    }

    return 0;
}

 

 

단절선 문제: 백준 11266

소스 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
#define fastio cin.tie(0)->sync_with_stdio(0)

using ll = long long;
using matrix = vector<vector<ll>>;
using vi = vector<int>;
using vb = vector<bool>;

int v, e, num=0;
vi graph[10'010];
vi visitno(10'010, 0);
vb cnt(10'010, false);

int dfs(int here, bool isroot) {
    visitno[here] = ++num; // 현재 방문 순서 저장 
    int ret = visitno[here]; // 방문 번호 최소값 저장 
    int child = 0; // dfs 탐색되는 자식의 갯수
    for(int i=0; i<graph[here].size(); ++i) {
        int there = graph[here][i];
        if(visitno[there]) {
            ret = min(ret, visitno[there]);
        }
        else {
            int minp = dfs(there, false); // 방문안한 노드를 탐색
            // root의 경우는 root보다 빠른 점이 없기 때문에 무조건 minp >= visitno[here]를 만족하므로 다른 조건 필요
            if(!isroot && minp >= visitno[here]) { // 루트가 아닐 경우, 방문안한 노드의 탐색 결과의 방문순서가 현재보다 크거나 같다면 단절점
                cnt[here] = true; 
            }
            ret = min(ret, minp);
            ++child;
        }
    }
    if(isroot && child>=2) { // root node의 경우는 previous의 기준이 없기 때문에 child 2개 이상으로 검출
        cnt[here] = true;
    }
    return ret;
}

int main() {
    fastio;
    cin >> v >> e;
    for(int i=0;i<e;++i) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(int i=1;i<=v;++i) {
        if(!visitno[i]) dfs(i, true);
    }
    int ans = 0;
    for(int i=1;i<=v;++i) {
        if(cnt[i]) ++ans;
    }
    cout << ans << '\n';
    for(int i=1;i<=v;++i) {
        if(cnt[i]) cout << i << ' ';
    }
    return 0;
}