무향 그래프에서 단절점 찾기 / 단절선 찾기

무향 그래프에서 단절점(Cut vertex) 찾기

단절점이란 해당 정점과 인접한 간선들을 모두 지웠을 때 해당 컴포넌트가 두 개 이상으로 나뉘어지는 정점을 말합니다.

아래 그림을 예시로 들었을 때, 1번 정점과 인접한 간선을 모두 지웠을 때, 0번 정점이 떨어져나가 하나의 컴포넌트가 됩니다. 그러므로 1번 정점은 단절점입니다.

마찬가지 이유로 3번, 5번 정점도 단절점입니다.

 

그림 1

 

단절점을 찾는 방법으로 여러가지가 있지만 DFS 탐색 1회만으로 그래프의 모든 단절점을 찾을 수 있습니다.

 

먼저 아무 정점으로부터 DFS 트리를 만듭니다. 이 때 임의의 정점 u와 연결된 정점들은 모두 u의 조상이거나 자손입니다.

그림 2

만약 u와 인접한 간선들을 모두 지웠을 때 그래프가 나눠지지 않는 경우는 u의 자손들이 u의 선조와 역방향 간선으로 연결되어 있을 때 입니다.

따라서 u의 자손들이 u의 선조와 역방향 간선으로 연결되어있다면 u는 단절점이 아닙니다.

또는 u가 DFS 트리의 루트라면 자손이 없거나 하나밖에 없는 경우는 단절점이 아닙니다.

 

이 알고리즘을 구현할 때는 각 정점의 DFS 발견 순서를 비교하는 형태로 코드를 작성하여 구현을 할 수 있습니다.

핵심은 어떤 서브트리가 u의 조상 중 하나와 연결되어있는지인데, u의 조상들은 항상 u보다 먼저 발견되었습니다.

노드들이 언제 발견되었는지를 저장하여 값을 비교해가며 DFS 탐색을 하면 단절점을 찾을 수 있습니다.

 

https://www.acmicpc.net/problem/11266

11266번: 단절점

#include <bits/stdc++.h>
 
using namespace std;
 
#define endl '\n'
#define int long long
 
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
const double EPS = 1e-9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
 
const int MAX = 100001;
vector<int> adj[MAX];
set<int> CutVertex;
int discovered[MAX];
int counter, V, E;
 
int findCutVertex(int curr, bool isRoot)
{
    discovered[curr] = ++counter;
    int ret = discovered[curr];
    int children = 0;
    for(int next : adj[curr])
    {
        if(discovered[next] == 0)
        {
            children++;
            int subtree = findCutVertex(next, false);
            if(!isRoot && subtree >= discovered[curr])
                CutVertex.insert(curr);
            ret = min(ret, subtree);
        }
        else ret = min(ret, discovered[next]);
    }
    if(isRoot && children > 1) CutVertex.insert(curr);
    return ret;
}
 
 
int32_t main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> V >> E;
    int u, v;
    for(int i=0;i<E;i++)
    {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    for(int i=1;i<=V;i++)
    {
        if(!discovered[i]) findCutVertex(i, true);
    }
 
    cout << CutVertex.size() << endl;
    for(int P : CutVertex)
        cout << P << ' ';
 
    return 0;
}

무향 그래프에서 단절선(Bridge) 찾기

단절선이란 그 간선을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 간선을 말합니다. 즉, 제거했을 때 그래프의 컴포넌트의 개수가 증가하는 간선을 말합니다.

 

위의 그램 1에서는 네 개의 간선 (0, 1), (3, 4), (5, 6), (5, 7)이 단절선이 됩니다.

가장 중요한 점으로 단절선은 항상 DFS 트리 간선일 수 밖에 없다는 것이 있습니다. 어떤 간선 (u, v)가 순방향 간선이나 역방향 간선이라면 u와 v를 잇는 또다른 경로가 있다는 것인데, 그러면 (u, v)는 결코 단절선이 될 수 없습니다.

 

DFS 트리 상에서 u가 v의 부모일 때, 트리 간선 (u, v)가 단절선이 되기 위해서는 v를 루트로 하는 서브트리와 이 외의 점들을 연결하는 유일한 간선이 (u, v)가 되어야 합니다.

따라서 (u, v)를 제외한 역방향 간선으로 u보다 높은 정점에 갈 수 없을 경우 (u, v)가 단절선이라고 판정할 수 있습니다.

 

 

 

#include <bits/stdc++.h>
 
using namespace std;
 
#define endl '\n'
#define int long long
 
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
const double EPS = 1e-9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
 
const int MAX = 100001;
vector<int> adj[MAX];
set<pii> bridge;
int discovered[MAX];
int counter, V, E;
 
int findBridge(int curr, bool isRoot, int prev=-1)
{
    discovered[curr] = ++counter;
    int ret = discovered[curr];
    vector<int> child;
    for(int next : adj[curr])
    {
        if(discovered[next] == 0)
        {
            int subtree = findBridge(next, false, curr);
            if(subtree > discovered[curr])
            {
                if(curr < next) bridge.insert({curr, next});
                else bridge.insert({next, curr});
            }
            ret = min(ret, subtree);
        }
        else if(next != prev) ret = min(ret, discovered[next]);
    }
    return ret;
}
 
 
int32_t main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> V >> E;
    int u, v;
    for(int i=0;i<E;i++)
    {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    for(int i=1;i<=V;i++)
    {
        if(!discovered[i]) findBridge(i, true);
    }
    cout << bridge.size() << endl;
    for(pii P : bridge)
        cout << P.first << ' ' << P.second << endl;
 
    return 0;
}