SCC, Tarjan Algorithm 연구 일지

SCC 알고리즘에는 Kosaraju Algorithm, Tarjan Algorithm이 있습니다.

Kosaraju 알고리즘이 구현에는 편하지만 타잔 알고리즘이 SCC 노드끼리의 위상 정렬을 알 수 있기 때문에 공부하였습니다.

 

제일 최신화된 연구일지는 22.04.23 연구일지입니다. 이를 참고하여 읽어주시길 바랍니다.

---

22.04.22 연구일지

Time Complexity

>> O(|V| + |E|)

 

동작 원리

+DFS와 Stack에 대한 사전 지식이 있어야 합니다.

 

1. 인접 배열을 이용한 DFS를 돌립니다.

2. DFS를 돌리면서 스택에 해당 노드를 담습니다.

    2.1 next 노드의 sccOrder가 정해져 있지 않다면 next 노드를 가지고서 DFS를 돌리고, 제일 작은 minOrder 갱신합니다.

    2.2 next 노드의 sccOrder가 정해져 있고, SCC 구성 노드가 아니라면 이미 방문했다는 뜻이므로 next 노드의 sccOrder와 minOrder 중 작은 것으로 minOrder를 갱신합니다.

3. (2.1)에서 nextOrder의 minOrder를 갱신해야 하므로 리턴 값은 minOrder입니다.

4. 재귀 함수들이 종료되면서 다시 돌아가는 노드 중 sccOrder와 minOrder가 같은 것이 있다면 스택에 담겨있던 노드들을 전부 pop 하며 하나의 SCC로 구성시킵니다. SCC로 구성되었다는 체크를 위해 isSCC bool 타입형 배열을 사용합니다.

 

+recursive call이 돌아가는 원리를 위해 minOrder와 실행 중인 노드의 sccOrder를 출력하는 코드를 짜두었습니다. (주석)

>> 스택에 담겨있는 노드들이 SCC로 구성되는 순간은 recursive call이 종료되면서 SCC를 구성하는 첫 번째 노드로 돌아오는 순간 실행되는 DFS에서 만들어지는 것을 알 수 있습니다. (minOrder와 DFS가 실행되는 노드의 sccOrder가 같을 때)

 

BOJ 2150

#include <iostream>
#include <vector>
#include <stack>
#include <memory.h>
#include <algorithm>
#define MAX 10001
using namespace std;

int v, e;
vector<int> adj[MAX];
stack<int> s;
int sccOrder[MAX];
bool isScc[MAX];
int order = 0; // order = 순서
vector<vector<int>> SCCs;

bool cmp(vector<int> a, vector<int> b){
    return a[0] < b[0];
}

int findScc(int now){ // DFS
    int minOrder = sccOrder[now] = ++order;
    s.push(now);
    
    for(int i = 0; i < adj[now].size(); i++){
        int next = adj[now][i];
        
        if(sccOrder[next] == -1){
            minOrder = min(minOrder, findScc(next));
        }
        else if(!isScc[next]){
            minOrder = min(minOrder, sccOrder[next]);
        }
    }
    
    //cout << minOrder << ' ' << sccOrder[now] << '\n';
    if(minOrder == sccOrder[now]){
        vector<int> tempScc;
        while(1){
            int temp = s.top(); s.pop();
            isScc[temp] = true;
            tempScc.push_back(temp);
            if(temp == now) break;
        }
        
        SCCs.push_back(tempScc);
    }
    
    return minOrder;
}

void tarjan(){
    memset(sccOrder, -1, sizeof(sccOrder));
    
    for(int i = 1; i <= v; i++){
        if(sccOrder[i] == -1){
            findScc(i);
        }
    }
}

int main(){
    cin >> v >> e;
    for(int i = 0; i < e; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
    }
    
    cout << '\n';
    tarjan();
    cout << '\n';
    
    for(int i = 0; i < SCCs.size(); i++){
        sort(SCCs[i].begin(), SCCs[i].end());
    }
    
    sort(SCCs.begin(), SCCs.end(), cmp);
    
    cout << SCCs.size() << '\n';
    for(int i = 0; i < SCCs.size(); i++){
        for(int j = 0; j < SCCs[i].size(); j++){
            cout << SCCs[i][j] << ' ';
        }
        cout << -1 << '\n';
    }
    
    return 0;
}

---

다음 연구 내용

SCC 위상 정렬 관련 포스팅 https://everenew.tistory.com/135

[백준] No.3997 - 축구 전술 (C++, SCC, 타잔 알고리즘)

+ 아직 해당 알고리즘 DFS의 recursive call 제대로 숙지되지 않음 변수명을 더 알아보기 쉽게 바꾸거나 해야 할 듯

>> 변수명도 윗 포스팅 참고할 것

---

22.04.23 연구일지 (1)

확실히 변수명과 간단하게 표현된 코드를 가독성 있게끔 수정하여 주었더니 편합니다.

그리고, '각 node당 parent(==minOrder)와 visitedOrder(==sccOrder)가 존재한다'라고 생각하는 것이 Tarjan Algorithm을 이해하는 데에 도움이 되었습니다.

구현을 스스로 한 번 더 해주면 도움이 될 거 같습니다.

 

그리고, 코드를 보면서 아래 그림에서 묶어둔 노드들은 코드에서 어떻게 돌아갈까를 생각해보면 이해하는 데에 도움이 될 것입니다.

 

 

Q1: 2, 3, 4가 하나의 SCC가 되는데 1부터 시작했을 텐데 그럼 1은 어떻게 처리될까?

 

A1: Node 4의 recursive call에서 nextNode가 !isSCC[next]조건에서 걸려서 parent는 2가 될 것이고, parent를 계속 리턴하며 recursive call이 계속 종료됩니다.(parent값은 2) visitedOrder[now]와 parent가 2로 같아지는 순간 스택에서 4, 3, 2 순서로 pop 하여 SCC로 구성될 것입니다. visitedOrder[now]와 parent가 같으면 break가 되기 때문에 1은 여전히 스택에 남아있을 것입니다. Node 2의 recursive call이 종료된 후, Node 1의 recursive call로 돌아와 parent는 min함수에 의해 1로 될 것이며 이는 또한, visitedOrder[now]와 parent가 1로 같다는 뜻이므로 1은 그 자체로 하나의 SCC가 되는 것을 의미합니다.

 

Q2: Node 5는 어떻게 하나의 SCC로 처리될까?

 

A2: Node 4와 인접해있기 때문에 A1에서 설명한 대로 Node 4의 recursive call의 순간을 주목해야 합니다. parent는 Node 2와 인접해있어서 parent는 2로 갱신되어있을 겁니다. for문으로 인해 다음 next node를 고려하며 Node 5로 가게 됩니다. Node 5는 아직 방문하지 않았기에 Node 5의 DFS recursive call로 들어가게 됩니다. Node 5와 인접해있는 노드가 없기 때문에 parent와 visitedOrder가 5로 같을 것입니다. 즉, 이는 하나의 SCC로 구성됨을 의미합니다.

 

>> QnA를 보면 min함수가 DFS내에서 어떤 역할을 하고 있는 것인지 인지하고 있는 것이 중요합니다.

 

BOJ 2150

#include <iostream>
#include <vector>
#include <stack>
#include <memory.h>
#include <algorithm>
#define MAX 10001
using namespace std;

int v, e;
vector<int> adj[MAX];
stack<int> s;
int visitedOrder[MAX];
bool isScc[MAX];
int order = 0; // order = 순서
vector<vector<int>> SCCs;

bool cmp(vector<int> a, vector<int> b){
    return a[0] < b[0];
}

int dfs(int now){ // DFS
    // 한 노드에게 parent와 자기자신의 visitedOrder가 있다고 생각할 것
    int parent = ++order;
    visitedOrder[now] = order;
    s.push(now);
    
    for(int i = 0; i < adj[now].size(); i++){
        int next = adj[now][i];
        
        if(visitedOrder[next] == -1){
            // nextNode가 방문이 되지 않았을 경우
            int nextOrder = dfs(next);
            parent = min(parent, nextOrder);
        }
        else if(!isScc[next]){
            // nextNode가 방문이 되어있고, SCC가 아닐 때
            // >> 사이클이 형성되었다는 의미이고, 이는 SCC임을 말한다.
            parent = min(parent, visitedOrder[next]);
        }
    }
    
    //cout << parent << ' ' << visitedOrder[now] << '\n';
    if(parent == visitedOrder[now]){
        vector<int> tempScc;
        while(1){
            int temp = s.top(); s.pop();
            isScc[temp] = true;
            tempScc.push_back(temp);
            if(temp == now) break;
        }
        
        SCCs.push_back(tempScc);
    }
    
    return parent;
}

void tarjan(){
    memset(visitedOrder, -1, sizeof(visitedOrder));
    
    for(int i = 1; i <= v; i++){
        if(visitedOrder[i] == -1){
            //cout << '\n';
            dfs(i);
            //cout << '\n';
        }
    }
}

int main(){
    cin >> v >> e;
    for(int i = 0; i < e; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
    }
    
    tarjan();
    
    for(int i = 0; i < SCCs.size(); i++){
        sort(SCCs[i].begin(), SCCs[i].end());
    }
    
    sort(SCCs.begin(), SCCs.end(), cmp);
    
    cout << SCCs.size() << '\n';
    for(int i = 0; i < SCCs.size(); i++){
        for(int j = 0; j < SCCs[i].size(); j++){
            cout << SCCs[i][j] << ' ';
        }
        cout << -1 << '\n';
    }
    
    return 0;
}

---

22.04.23 연구일지 (2)

Topological Sort in SCC

Tarjan Algorithm을 공부하게 된 이유입니다. Tarjan Algorithm을 이용하면 SCC끼리의 Topological Sort를 구할 수 있습니다.

 

indegree가 생기게 되는 케이스는 2가지가 있습니다.

• 인접 배열에서 next node가 이미 SCC인 경우
• SCC를 만들 때(stack pop), stack이 empty상태가 아닌 경우, 남아있는 node가 만들어지는 SCC를 가리킵니다.

sccnum 배열을 만들어서 각 node들이 어떤 SCC에 속하는지를 알고, indegree 배열을 만들어서 SCC마다의 indegree를 count 해주면 됩니다. indegree의 index는 각 SCC의 번호입니다. (sccCnt)

 

BOJ 3997

#include <iostream>
#include <vector>
#include <stack>
#include <memory.h>
#include <algorithm>
#define MAX 100001
using namespace std;

int T;
int v, e;
vector<int> adj[MAX];
vector<vector<int>> SCC;
int visitedOrder[MAX];
int sccnum[MAX]; // node들이 어떤 SCC에 속해있는지 확인
int indegree[MAX]; // SCC area node끼리의 indegree를 고려함
stack<int> s;
int order = 0;
int sccCnt = 0;

int dfs(int now){
    int parent = visitedOrder[now] = ++order;
    s.push(now);
    
    for(int i = 0; i < adj[now].size(); i++){
        int next = adj[now][i];
        
        if(visitedOrder[next] == -1){ // 방문하지 않았다면
            parent = min(parent, dfs(next));
        }
        else if(sccnum[next] == -1){
            // SCC parent 갱신?
            parent = min(parent, visitedOrder[next]);
        }
        else{
            // 이미 SCC로 구성된 노드에 진입을 하려한다면
            // 해당 SCC의 진입차수가 하나 커진다.
            indegree[sccnum[next]]++;
        }
    }
    
    if(parent == visitedOrder[now]){
        vector<int> scc;
        while(1){
            int temp = s.top(); s.pop();
            sccnum[temp] = sccCnt;
            scc.push_back(temp);
            if(temp == now) break;
        }
        SCC.push_back(scc);
        
        // 스택이 비어있지 않다는 건 방금 만들어진 SCC로 가는
        // 진입차수가 존재한다는 뜻이다.
        if(!s.empty()) ++indegree[sccCnt];
        ++sccCnt;
    }
    
    return parent;
}

void tarjan(){
    memset(visitedOrder, -1, sizeof(visitedOrder));
    memset(indegree, 0, sizeof(indegree));
    memset(sccnum, -1, sizeof(sccnum));
    order = 0, sccCnt = 0;
    
    if(!s.empty()) s.pop();
    
    for(int i = 0; i < v; i++){
        if(visitedOrder[i] == -1) dfs(i);
    }
}

int main(){
    
cin >> T;
while(T--){
    SCC.clear();
    for(int i = 0; i < MAX; i++){
        adj[i].clear();
    }
    
    cin >> v >> e;
    for(int i = 0; i < e; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
    }
    
    tarjan();
    
    int indegreeCntZero = 0;
    int ansSCCnum;
    for(int i = 0; i < sccCnt; i++){
        if(indegree[i] == 0){
            ansSCCnum = i;
            indegreeCntZero++;
            //cout << i << ' ';
        }
    }
    
    if(indegreeCntZero == 1){
        sort(SCC[ansSCCnum].begin(), SCC[ansSCCnum].end());
        for(int i = 0; i < SCC[ansSCCnum].size(); i++){
            cout << SCC[ansSCCnum][i] << '\n';
        }
    }
    else{
        cout << "Confused" << '\n';
    }
    
    cout << '\n';
}
    return 0;
}

---

Tarjan Algorithm Key Point

Operating

• 각 node에는 visitedOrder와 parent가 존재한다는 것을 인지
•  min function의 역할이 무엇인지 인지

Topological Sort in SCC

• 각 노드가 어떤 SCC에 속하는지 sccnum이라는 배열의 필요
• 어떤 경우에 SCC에 indegree가 생기는지를 인지