[백준] 2150번 Strongly Connected Component C++ 코드

코드 (코사라주 알고리즘)

#include <iostream>
#include <vector>
#include <cstring>
#include <map>
#include <cmath>
#include <algorithm>
#include <queue>
#include <string>
#include <stack>

using namespace std;
const int MAX_N = 10003;
int v, e, a, b, cnt = 1, visited[MAX_N];
bool finished[MAX_N];
vector<int> adj[MAX_N], radj[MAX_N];
vector<vector<int>> res;
stack<int> stk;

void dfs(int x) {
    visited[x] = 1;
    for(int i : adj[x]) {
        if(!visited[i]) {
            dfs(i);
        }
    }
    stk.push(x);
}

void dfs2(int x, vector<int> &scc) {
    visited[x] = 1;
    scc.push_back(x);
    for(int i : radj[x]) {
        if(!visited[i]) {
            dfs2(i, scc);
        }
    }
}

void FASTIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int main() {
    FASTIO();
    cin >> v >> e;
    for(int i = 0; i < e; i++) {
        cin >> a >> b;
        adj[a].push_back(b);
        radj[b].push_back(a);
    }
    fill(visited, visited + MAX_N, 0);
    for(int i = 1; i < v + 1; i++) {
        if(!visited[i]) {
            dfs(i);
        }
    }
    fill(visited, visited + MAX_N, 0);
    while(!stk.empty()) {
        int node = stk.top();
        stk.pop();
        if(!visited[node]) {
            vector<int> scc;
            dfs2(node, scc);
            sort(scc.begin(), scc.end());
            res.push_back(scc);
        }
    }
    sort(res.begin(), res.end());
    cout << res.size() << '\n';
    for(const auto& scc : res) {
        for(int node : scc) {
            cout << node << " ";
        }
        cout << "-1\n";
    }
    return 0;
}

코드 (타잔 알고리즘)

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

const int MAXN = 10003; // 최대 노드 수

int n, m, idCounter;
int discovery[MAXN];    // 각 노드의 발견 순서 저장
vector<int> adj[MAXN];  // 인접 리스트
vector<vector<int>> sccResult; // SCC 결과 저장
stack<int> stk;
bool finished[MAXN];    // 각 노드의 SCC 포함 여부

// DFS를 이용한 SCC 탐색
int dfs(int node) {
	discovery[node] = ++idCounter; // 노드의 발견 순서 저장
	stk.push(node);

	int lowLink = discovery[node];
	for (int next : adj[node]) {
		if (!discovery[next]) {
			// 아직 방문하지 않은 노드라면 DFS 재귀 호출
			lowLink = min(lowLink, dfs(next));
		}
		else if (!finished[next]) {
			// 이미 방문했으나 SCC에 포함되지 않은 노드 처리
			lowLink = min(lowLink, discovery[next]);
		}
	}

	// SCC 찾음: 시작 노드와 같은 발견 순서를 가진 경우
	if (lowLink == discovery[node]) {
		vector<int> scc;
		while (true) {
			int topNode = stk.top();
			stk.pop();
			finished[topNode] = true; // SCC에 포함된 노드 표시
			scc.push_back(topNode);
			if (topNode == node) break;
		}
		sort(scc.begin(), scc.end()); // 결과를 오름차순으로 정렬
		sccResult.push_back(scc);     // 결과에 추가
	}
	return lowLink;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int from, to;
		cin >> from >> to;
		adj[from].push_back(to);
	}

	for (int i = 1; i <= n; i++) {
		if (!discovery[i]) {
			dfs(i);
		}
	}

	sort(sccResult.begin(), sccResult.end()); // SCC 그룹을 오름차순 정렬
	cout << sccResult.size() << '\n';
	for (const auto& scc : sccResult) {
		for (int node : scc) {
			cout << node << " ";
		}
		cout << "-1\n";
	}
	return 0;
}

풀이

강한 연결 요소(SCC)를 공부할 수 있었던 문제. 따로 포스팅을 하겠지만 코사라주 알고리즘은 dfs 2번, 타잔 알고리즘은 dfs 1번으로 강한 연결 요소를 찾아낸다. 강한 연결 요소는 위상 정렬과 연관되어 자주 나온다고 하니 기억하는 게 좋을 것 같다.