Algorithm in A..Z - SSC(Tarjans)

개념

강한 연결 요소(Strongly Connected Component)는 방향 그래프에서 서로 왕복할 수 있는 가장 큰 정접들의 집합입니다.

Strongly Connected Component

 

---

작동원리

1. DFS를 하면서 방문하는 순서대로 값을 할당하고, 스택에 넣는다.

2. DFS를 하면서 방문하지 않는 정점이나, 방문했지만 아직 SCC에 속하지 않은 정점들에게 할당된 값 중 가장 작은 값을 리턴한다.

3. 자신에게 할당된 값과 리턴값이 같으면 SCC이다.

 

* 타잔 알고리즘은 스택을 사용하여 SCC를 추가하기 때문에 위상정렬이 된다.

---

시간복잡도

1. DFS할 때 O(V + E)

 

O(V + E)

---

문제

2150 Strongly Connected Component

www.acmicpc.net/problem/2150

2150번: Strongly Connected Component

---

코드

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

bool op(vector<int> &ve1, vector<int> &ve2) {
    return ve1.front() < ve2.front();
}

int v, e;
vector<vector<int>> graph;

vector<vector<int>> scc;
vector<int> visitNumber, sccNumber;

int n;
stack<int> st;
int dfs(int now) {
    visitNumber[now] = n++;
    st.push(now);

    int result = visitNumber[now];
    for (auto &next : graph[now]) {
        if (visitNumber[next] == -1) {
            result = min(result, dfs(next));
        } else if(sccNumber[next] == -1) {
            result = min(result, visitNumber[next]);
        }
    }

    if (visitNumber[now] == result) {
        vector<int> cycle;

        while (!st.empty()) {
            int i = st.top();st.pop();

            cycle.push_back(i);
            sccNumber[i] = scc.size();
            if (i == now) {
                break;
            }
        }
        sort(cycle.begin(), cycle.end());
        scc.push_back(cycle);
    }

    return result;
}

int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    cin >> v >> e;

    graph.resize(v + 1);
    while (e--) {
        int v1, v2;
        cin >> v1 >> v2;

        graph[v1].push_back(v2);
    }

    visitNumber.assign(v + 1, -1);
    sccNumber.assign(v + 1, -1);
    for (int i = 1;i <= v;++i) {
        if (visitNumber[i] == -1) {
            dfs(i);
        }
    }

    cout << scc.size() << "\n";
    sort(scc.begin(), scc.end(), op);
    for (auto &ve : scc) {
        for (auto &index : ve) {
            cout << index << " ";
        }
        cout << -1 << "\n";
    }
}