[C++] 강한 연결 요소(타잔, 코사라주)

강한 연결 요소(Strongly Connected Component)

• 두 정점에 대해 양방향으로 이동 가능한 경로가 모두 있을 때 두 정점은 같은 강 결합 컴포넌트(SCC)에 속한다. 즉, 그래프의 사이클에서 같은 사이클 내에 존재하는 정점들은 같은 SCC에 속한다고 할 수 있다.
• 방향 그래프에서만 정의된다.

 

1. 타잔 알고리즘

1) 기본 원리

• 깊이 우선 탐색
• 방향 그래프의 정점들을 방문한 후 방문한 정점의 간선을 통해 상위에서 방문된 정점을 방문한다면 SCC가 존재한다고 판단한다.

Tarjan algorithm

 

2) 문제

 

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

2150번: Strongly Connected Component

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

vector<int> graph[10001];

vector<vector<int>> groups;
stack<int> group; // 방문한 노드들
bool grouped[10001]; // 그룹핑
int check[10001]; // 방문 순서
int num = 0; // 방문 순서 인덱스

int dfs(int index)
{
    check[index] = ++num;
    group.push(index);

    int parent = check[index];
    for (int i = 0; i < graph[index].size(); i++) {
        int child = graph[index][i];

        if (!check[child])
            parent = min(parent, dfs(child));
        else if (!grouped[child])
            parent = min(parent, check[child]);
    }

    if (parent == check[index])
    {
        vector<int> v;
        while (true) {
            int t = group.top();
            group.pop();

            grouped[t] = true;
            v.push_back(t);

            if (t == index)
                break;
        }

        sort(v.begin(), v.end());
        groups.push_back(v);
    }

    return parent;
}

int main()
{
    int V, E;
    cin >> V >> E;

    for (int i = 0; i < E; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
    }

    for (int i = 1; i <= V; i++)
        if (!check[i])
            dfs(i);

    sort(groups.begin(), groups.end());

    cout << groups.size() << '\n';
    for (int i = 0; i < groups.size(); i++) {
        for (int j = 0; j < groups[i].size(); j++)
            cout << groups[i][j] << ' ';
        cout << "-1\n";
    }
}

 

2. 코사라주 알고리즘

1) 기본 원리

• 깊이 우선 탐색
• 탐색이 종료되는 순서대로 정점을 스택에 저장하고 스택의 상단부터 역방향 그래프를 타고 DFS을 수행한다.

 

2) 문제

 

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

2150번: Strongly Connected Component

#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
#include <algorithm>
using namespace std;

vector<int> graph[10001], rev_graph[10001];

vector<vector<int>> groups(10001);
stack<int> nodes;
bool check[10001];
int groupsCount = 0;

void dfs(int index)
{
	if (check[index])
		return;

	check[index] = true;
	for (int i = 0; i < graph[index].size(); i++)
		dfs(graph[index][i]);

	nodes.push(index); // 탐색이 종료되면 정점 저장
}

void rev_dfs(int index)
{
	if (check[index])
		return;

	check[index] = true;
	groups[groupsCount].push_back(index);
	for (int i = 0; i < rev_graph[index].size(); i++)
		rev_dfs(rev_graph[index][i]);
}

int main()
{
	int V, E;
	cin >> V >> E;
	for (int i = 0; i < E; i++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		rev_graph[b].push_back(a);
	}

	for (int i = 1; i <= V; i++)
		if (!check[i])
			dfs(i);

	memset(check, false, sizeof(check));
	while (!nodes.empty()) {
		if (!check[nodes.top()]) {
			rev_dfs(nodes.top());

			sort(groups[groupsCount].begin(), groups[groupsCount].end());
			groupsCount++;
		}

		nodes.pop();
	}

	sort(groups.begin(), groups.begin() + groupsCount);

	cout << groupsCount << '\n';
	for (int i = 0; i < groupsCount; i++) {
		for (int j = 0; j < groups[i].size(); j++)
			cout << groups[i][j] << ' ';
		cout << "-1\n";
	}
}