[강한 연결 요소 SCC] - BOJ_2150 : Strongly Connected Component

오늘은 SCC 알고리즘에 대해 공부하였다.

강한 연결요소인 SCC를 구하는 문제였다.

2-sat을 풀기전 사전 준비로 풀었는데, 어려웠다..

💡SCC 알고리즘이란?

scc란 쉽게 말하면 전체 노드 집합 속에서, 서로 사이클을 이루는 노드들의 집합이다.

이런 형태의 노드 집합이 있으면

전체 집합을 이렇게 3개의 scc집합 (사이클) 로 나누는 것이다.

scc를 구할때는 코사라주 알고리즘과 타잔 알고리즘 두가지 종류가 있는데,

타잔알고리즘이 구현이 어려운 대신 범용성이 넓기에 타잔 알고리즘을 사용해 풀었다.

 

🐒타잔 알고리즘이란?

타잔 알고리즘이란 SCC를 구하는 기법중 하나로, DFS 탐색을 들어갈 때 나의 부모노드를 기록하면서 가는 것이다.

스택에 방문한 노드들을 넣으면서 DFS를 돌다가 나 자신이 부모노드가 되면, (즉 나의 자식노드중에서 나에게로 돌아오는 것이 없거나 있고, 나 또한 나보다 더 먼저 DFS가 들어간 노드가 존재하지 않는다면 ) 스택에서 현재 방문 노드가 나올 때까지 스택에 존재하는 모든 노드를 뺀다. 그러면 해당 집합은 새로운 SCC가 되는 것이다.

 

👀타잔 알고리즘 예시

먼저 첫번째 SCC를 구하는 과정이다.

1번 노드부터 DFS를 시작하여, DFS가 끝났음에도 자신의 부모노드가 없음을 확인할때까지 DFS 탐색을 들어간다.

이때, 3번노드를 방문했을 때 3번노드에서 더 이상 DFS를 들어갈 수 없음이 판별이 될 경우 탐색을 종료하고 스택에서 현재 방문 노드인 3이 나올때까지 POP을 진행한다. 하지만 3의 자식 노드가 없어 STACK에서는 3만 나오게 되고, 첫번째 SCC 그룹에는 3만 들어가게 된다.                                                                            

이후 다시 8의 다음 연결 노드인 7을 확인한다. 이때 7은 자신의 DFS가 끝났음을 깨닫고, 자신보다 더 높은 부모노드가 존재하지 않는지를 확인한다.(이 부분이 구현이 어려움) 이후, 스택에서 7이 나올때까지 POP을 진행하고 7 6 8은 두번째 SCC 그룹이 된다. 이후, 5에서 다음 DFS인 4를 방문하고, 4가 1을 방문하며 1의 DFS가 끝이 나게되고, 1 2 5 4 또한 마지막으로 SCC를 이루게 되며 모든 노드가 SCC그룹에 속한 채로 끝이 나게 된다.

 

📜CODE

#include <bits/stdc++.h>
#define GuardiansOfGalaxy3_ZonZam 1
using namespace std;

int n,e;
vector<int> vertex[10'001];
int visited[10'001];
int discover[10001];
stack<int> stk;
vector<vector<int>> scc;
vector<int> answer[10001];
int sequence[10'001];
int t=1;

void addScc(int x);

int makeScc(int cur){ 
    discover[cur]=1;
    sequence[cur]=t++;          //방문 순서대로 id 발급
    int parent=sequence[cur];
    
    stk.push(cur);

    int Nnode;
    for(int i=0; i<vertex[cur].size(); i++){
        Nnode=vertex[cur][i];
        if(visited[Nnode]) continue;  //이미scc를 이룬 노드를 방문
        if(discover[Nnode]){   // 방문할 노드가 scc를 이루지 않았지만 이미 방문되었을때 (즉 사이클을 이룰때)
            parent=min(parent,sequence[Nnode]);     //부모를 해당 노드로 바꾸고 다시 자식 dfs 탐색
            continue;
        }
        parent=min(parent,makeScc(Nnode));   //가장 먼저 방문한 노드가 부모가 된다
    }

    if(parent==sequence[cur]){  //자식중에 나에게 돌아오는 노드가 없거나, 있을 때 모두 해당 즉, 내가 자식이 아닐 때
        addScc(cur);
    }
    
    return parent;
}

void addScc(int cur){
    vector<int> newScc;
    int tmp;
    while(true){
        tmp=stk.top();
        newScc.push_back(tmp);
        visited[tmp]=GuardiansOfGalaxy3_ZonZam; //현재 요소가 scc를 이룸
        stk.pop();
        if(tmp==cur){
            break;
        }
    }
    scc.push_back(newScc); //전체 scc 벡터에 현재 생성한 scc를 insert
    return;
}

int main(){
    cin.tie(0)->ios::sync_with_stdio(0);
    cin>>n>>e;

    int Pnode,Nnode;
    while(e--){
        cin>>Pnode>>Nnode;
        vertex[Pnode].push_back(Nnode);
    }
    for(int i=1; i<=n; i++){
        if(!discover[i])
            makeScc(i);
    }
    int cnt=0;
    for(auto curScc: scc){
        cnt++;
        sort(curScc.begin(),curScc.end());
        answer[curScc[0]]=curScc;
    }
    cout<<cnt<<'\n';
    for(auto &c: answer){
        if(!c.empty()){
            for(auto &i:c){
                cout<<i<<" ";
            }
            cout<<"-1"<<'\n';
        }
    }

}

 

이 문제를 풀면서 애먹었던 부분은 이부분인데,

 if(discover[Nnode]){   // 방문할 노드가 scc를 이루지 않았지만 이미 방문되었을때 (즉 사이클을 이룰때)
            parent=min(parent,sequence[Nnode]);     //부모를 해당 노드로 바꾸고 다시 자식 dfs 탐색
            continue;
        }

이미 방문한 노드를 만났을때 parent를 내가 이번에 만난 노드의 sequence번호와 현재 parent값을 비교해주지 않아서였다. (기존에는 parent를 바로 sequence[Nnode]로 만들어주었다.)

위 min 비교작업을 해주지 않을 시 생기는 반례로는

다음과 같은 경우가 존재한다.

위와 같은 경우, 2의 dfs가 2->1 ,2->3, 2->4  순으로 진행이 될 경우 2의 parent가 1이 되었다가 3으로 dfs 탐색을 들어가고, 4가 방문상태가 된 뒤 다시 2에서 4를 방문할 때 2의 parent가 4가 되는 불상사가 생기게 된다.. 아 뿔 싸 ! 

 

참고자료

• https://hyeo-noo.tistory.com/130
• https://storyofvector7.tistory.com/44