모든 Mother Vertex를 O(V+E)에 구하는 알고리즘

발행일 : 2020-07-08

UPD1 : 2020-09-25

Find All Mother Vertices in a directed graph.

 

Mother Vertex. 

어떤 방향 그래프에서 한 정점이 다른 모든 정점에 도달할 수 있다면 이를 Mother Vertex라 부른다.

 

 

 

이 글에서는 방향 그래프에서 존재하는 모든 Mother Vertex를 구하는 방법에 대해 알아본다.

 

 

Existence of a Mother Vertex

Mother Vertex의 존재성을 판정하는 방법은 두가지가 있다.

첫번째 방법은 각 정점에서 방문이 가능한 정점을 저장하는 bitset을 생성한다. 모든 비트가 체크된 노드가 있다면 그것은 Mother Vertex이다. 

DFS를 통해 bitset을 갱신한다. 주의할 것은 한번의 dfs를 실행했을 때 모든 노드를 방문하는 것은 맞지만 모든 bitset이 완전한 상태로 갱신되지는 않는다는 것이다. 인접한 모든 노드들의 비트셋이 '최신' 상태이고, 자신의 노드가 그 상태들을 모두 반영한 후에 모든 노드가 정확한 방문가능정점 bitset이 생긴다. 

(이와 관련한 다른 방법 및 구현은 링크 참고)

 

두번째 방법은 Mother Vertex가 존재한다면 DFS 시 마지막으로 종료되는 정점이 Mother Vertex인 사실을 이용한다.

정당성을 증명해보겠다.

마지막으로 종료된 정점을 v라 하자.

가정 : v는 Mother Vertex가 아니다.

Mother vertex가 존재한다 가정했으므로 그 중 한 mother vertex을 u라 하자.

두 가지 case가 있다.

Case#1 u가 v보다 먼저 dfs호출되었다.

u가 부모정점이므로 u에서 v로 가는 경로가 존재한다. 즉 u가 v보다 늦게 종료한다. v가 마지막으로 종료된 것에 모순.

Case#2 v가 u보다 먼저 dfs호출되었다.

v에서 u로 가는 경로가 존재하거나, 존재하지 않을 것이다.

만약 존재하지 않는다면 v가 u보다 먼저 종료된다. v가 마지막으로 종료된 것에 모순.

만약 존재한다면 v에서 u로 갈 수 있고, u가 mother vertex이므로 v 또한 mother vertex이다. 가정에 모순.

즉, 마지막으로 종료된 정점 v는 반드시 Mother Vertex이다. 다시 말하면 만약 v가 Mother Vertex가 아니라면 그 그래프에는 Mother Vertex가 없다.

 

이제 Mother Vertex를 판정하는 것은 다음과 같다.

1.그래프를 dfs 순회한다.

2.마지막으로 종료된 정점에서 dfs를 돌려 모든 정점에 도달 가능한지 판정한다.

가능하다면 v가 Mother Vertex, 아니라면 그래프에는 Mother Vertex가 없다.

 

Count the Number of Mother Vertices

만약 Mother Vertex의 개수를 구해야 한다면 어떻게 할까? 2번째 방법은 최대 1개의 Mother Vertex를 찾아준다. 

이를 이용하여 모든 Vertex Node를 구하려면 Mother Vertex를 구하고 이를 삭제하는 과정을 반복해야 한다.

O(V(V+E))의 시간 복잡도를 가진다. V가 10000보다 클 때 1초 내에 동작하지 않을 확률이 높다.

 

Better Approach

주어진 그래프를 Strongly Connected Component로 분리하자.

Mother Vertex가 존재한다면 모두 같은 SCC에 속한다는 것을 알 수 있다.

만약 서로 다른 Mother Vertex가 다른 SCC에 속한다면 Mother Vertex들간 경로가 존재하기 때문에 두 SCC가 하나로 합쳐진다. 즉, 그들은 같은 SCC에 속해있는 것이다. (SCC는 최대크기의 노드집합이다)

 

SCC를 구한 후 각각의 SCC를 정점으로 하는 SCC 그래프를 생각하자.

Source(Out-Degree가 0인 Component)의 경우 SCC 그래프의 Mother Vertex가 될 수 있다.

SCC 그래프에는 사이클이 없어야 하므로 1개 이하의 Mother Vertex가 존재해야 함에 유의하라.

Mother Vertex 판정법을 이용해 1개의 Mother Vertex Component를 찾으면 그 Component에 속한 모든 정점이 원래 그래프의 Mother Vertex이다. Mother Component의 정점의 개수를 출력하면 된다.

모든 과정의 시간복잡도가 O(V+E)이므로 전체 알고리즘의 시간복잡도는 O(V+E)이다.

 

*연습문제

백준 3977 축구 전술

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

3977번: 축구 전술

 

Code SASA 2361 대치갱's Instagram

https://code.sasa.hs.kr/problem.php?id=2361

SASA OJ

해결코드

colorscripter.com/s/dq1y1vx

#include<bits/stdc++.h>
using namespace std;
// Mother Vertex를 찾자
//https://cs.stackexchange.com/questions/84920/mother-vertex-of-a-graph
//1st approach : use bitmasks
//2rd approach : use SCC and find one source components
//3rd approcch : find SCC and find a Mother Vertex SCC
//https://www.acmicpc.net/problem/2150
int n,m,VIP;
vector<vector<int>> v,rev,SCC;
vector<int> f,grp,visit;
int id=0;
void dfs(int k){
    visit[k]=1;
    for(int i:v[k])
        if(!visit[i])
            dfs(i);
    f.push_back(k);
}
void Adfs(int k){
    visit[k]=1; grp[k]=id;
    SCC[id].push_back(k); 
    for(int i:rev[k]) 
        if(!visit[i])
            Adfs(i);
}
void SCC_DFS(int k){
    visit[k]=1;
    for(int c:SCC[k])
        for(int nxt:v[c])
            if(!visit[grp[nxt]])
                SCC_DFS(grp[nxt]);
}
int Mother_Vertex_SCC(){
    visit.assign(id+1,0);
    int v=-1;
    for(int i=0;i<id;i++){
        if(!visit[i]){
            SCC_DFS(i);
            v=i;
        }
    }
    visit.assign(id+1,0);
    SCC_DFS(v);
    for(int i=0;i<id;i++){
        if(!visit[i]){
            v=-1;
            break;
        }
    }
    return v;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m;
    v.resize(n+1); rev.resize(n+1); visit.resize(n+1);
    while(m--){
        int a,b;
        cin>>a>>b;
        v[b].push_back(a); //a가 b를 follow =>b의 follower 중 한명은 a
        rev[a].push_back(b);
    }
    for(int i=1;i<=n;i++)
        if(!visit[i])
            dfs(i);
    visit.assign(n+1,0); grp.resize(n+1);
    for(auto iter=f.rbegin();iter!=f.rend();iter++){
        int k=*iter;
        if(visit[k]) continue;
        //id = 0
        SCC.push_back(vector<int>(0)); //v[id] -> vector : 새로운 SCC
        Adfs(k); 
        ++id;
    }
    cin>>VIP;
    //id -> SCC의 수
    int P=Mother_Vertex_SCC();
    if(P==-1){
        cout<<"NO"<<'\n'<<0;
    }else{
        cout<<((grp[VIP]==P)?"YES":"NO")<<'\n';
        cout<<SCC[P].size();
    }
}
/**************************************************************
    Problem: 2361
    User: pentagon03
    Language: C++
    Result: Accepted
    Time:12 ms
    Memory:3652 kb
****************************************************************/