Scc

SCC

Topological Sort 등을 비롯한 많은 Directed Graph 에 대한 알고리즘은 DAG(Directed Acyclic Graph) 를 요구한다. 그래서 Graph 의 정보를 유지하면서 Cycle 을 제거할 필요성이 생겼고, 이를 위한 알고리즘이 SCC 이다.

A directed graph is called strongly connected if there is a path in each direction between each pair of vertices of the graph

A strongly connected component of a directed graph G is a subgraph that is strongly connected, and is maximal with this property: no additional edges or vertices from G can be included in the subgraph without breaking its property of being strongly connected.

위키의 위 두 문장이 SCC 를 정의한다. 즉 Directed Graph 의 Strongly Connected Subgraph 중 더이상 Vertex 를 추가할 수 없는 것들이다.

Graph 의 SCC 를 하나의 Vertex 로 치환하는 것을 Graph Condensation 이라고 하며 그 결과는 여러 유용한 특징을 갖는다.

1. DAG(Directed Acyclic Graph) 를 만족한다. 이에 대한 증명은 DAG 가 아닐 시 SCC 가 그 속성을 유지하면서 Vertex 를 넣을 수 없음과 모순된다는 걸 이용하면 쉽게 증명할 수 있다.
2. Edges 의 방향을 바꾸면 Edge 의 방향만 다른 결과를 낳는다. Edges 의 방향이 반대로 되어도 SCC 의 구성이 바뀌지 않기 때문이다.

SCC 를 이용해 여러 문제를 풀 수 있고, 이를 구하는 방법도 여러가지가 있다.

여기선 DFS 를 이용해 O(\(\vert V \vert + \vert E \ vert\)) 내에 구하는 두가지 유명 알고리즘만 정리한다. 아래 코드는 BOJ 문제 의 풀이코드이다.

Kosaruju Algorithm

코드

vector<int> lines[10001], tlines[10001]; // 정방향, 역방향 간선
bool visits[10001];
stack<int> records;

void DFS(int cur)
{
	if (visits[cur]) return;
	visits[cur] = true;

	for (auto l : lines[cur])
		DFS(l);

	records.push(cur);
}

void SCC(int cur, vector<int>& sets)
{
	if (!visits[cur]) return;
	visits[cur] = false;

	for (auto l : tlines[cur])
		SCC(l, sets);

	sets.push_back(cur);
}

int main()
{
	// Input
	int n, e; cin >> n >> e;
	for (int i = 1; i <= e; i++)
	{
		int a, b; cin >> a >> b;
		lines[a].push_back(b);
		tlines[b].push_back(a);
	}

	// 코사라주
	vector<vector<int>> sets;
	for (int i = 1, time = 0; i <= n; i++)
		DFS(i);
	while (1)
	{
		while (!records.empty() && !visits[records.top()]) records.pop();
		if (records.empty()) break;
		SCC(records.top(), sets.emplace_back()); 
		records.pop();
	}

	// 정렬 후 출력
	for (auto iter = sets.begin(); iter != sets.end(); iter++)
		sort(iter->begin(), iter->end());
	sort(sets.begin(), sets.end(), [](vector<int>& a, vector<int>& b) { return a[0] < b[0]; });
	
	cout << sets.size() << '\n';
	for (auto iter = sets.begin(); iter != sets.end(); iter++)
	{
		for (auto a : *iter) cout << a << ' ';
		cout << -1 << '\n';
	}
}

설명

DFS 를 두번 돌린다.

• 첫번째 DFS 는 Node 방문이 끝났을 때의 시점을 기록한다. 역방향이 필요하므로 Stack 을 이용해 이를 구현한다.
• 두번째 DFS 는 역간선을 이용해 가장 나중에 끝난 Node 부터 탐색한다. 이때 방문하는 Node 들은 하나의 SCC 에 소속된다.

증명은 간단하다. SCC 인 A, B 가 있어서 A 의 Node 부터 DFS 를 한다고 하자.

• A 와 B 는 SCC 의 정의 상 양방향으로 연결되지 않는다.
• A 에서 B 로 연결된 간선이 존재한다고 하자. DFS 는 A 를 걸쳐서 B 로 갈 수 밖에 없으므로 B 의 탐색이 종료되고 A 가 종료된다. 이 때 역방향 간선 중에는 A 에서 B 로 연결된 간선이 전제 상 없다. 그럼 두번째 DFS 에서 A 를 먼저 탐색하고 이때 B 를 방문하지 않음이 보장된다.
• B 에서 A 로 연결된 간선이 존재한다고 하자. 그러면 A 를 탐색 후 B 를 탐색하므로 두번째 DFS 에선 B 를 먼저 탐색하게 된다. 전제 상 역간선 중에는 B 부터 A 로 연결된 간선이 존재하지 않는다. 그러므로 두번째 DFS 에서 B 를 탐색 시 A 를 방문하지 않음이 보장된다.
• A 와 B 사이에 아무 간선이 없는 경우 별개의 Graph 라고 생각하고 각각 수행한 후 합치면 되므로 논외.

정의 상 SCC 내부에선 역간선을 이용해 탐색해도 모든 Node 를 방문한다. 그러므로 두번째 DFS 에서 이미 방문한 Node 를 재방문하지 않는다면 SCC 를 구할 수 있다. 증명 끝.

특징

두번째 DFS 의 방문 순서대로 위상정렬이 되어있다는 특징이 있다.

Tarjan Algorithm

코드

vector<int> lines[10001];
stack<int> st;
int visits[10001], n_visit;
int roots[10001], n_roots;

int SCC(int cur)
{
	int res = visits[cur] = ++n_visit;
	st.push(cur);

	for (auto l : lines[cur])
	{
		if (roots[l]) continue;
		if (visits[l]) res = min(res, visits[l]);
		else res = min(res, SCC(l));
	}

	if (res == visits[cur])
	{
		n_roots++;
		while (1)
		{
			int tmp = st.top();
			roots[tmp] = n_roots;
			st.pop();
			if (tmp == cur) break;
		}
	}
	return res;
}

int main()
{
	int n, e; cin >> n >> e;

	for (int i = 1; i <= e; i++)
	{
		int a, b; cin >> a >> b;
		lines[a].push_back(b);
	}

	for (int i = 1; i <= n; i++) if(!visits[i]) SCC(i);

	vector<vector<int>> sets(n_roots);
	for (int i = 1; i <= n; i++)
		sets[roots[i] - 1].push_back(i);
	sort(sets.begin(), sets.end(), [](auto& a, auto& b) { return a[0] < b[0]; });

	cout << sets.size() << '\n';
	for (auto iter = sets.begin(); iter != sets.end(); iter++)
	{
		for (auto a : *iter) cout << a << ' ';
		cout << -1 << '\n';
	}
}

설명

Tarjan Algorithm 은 SCC 의 어떠한 Node 도 그것을 Root 로 한 Spanning Tree 가 SCC 를 포함한다는 사실을 이용한다. 이는 Spanning Tree 를 이용하기 때문에 Articulation(단절점) 알고리즘과 흡사하다.

SCC 를 Vertex 하나로 대체한 Graph 가 DAG 이고 DAG 에는 하나 이상의 Leaf Node 가 있다. Leaf Node 에 해당되는 SCC 에서는 그 안에서 밖으로 나가는 Edge 가 존재하지 않는다. 그러므로 Spanning Tree 를 만들었을 때 하나의 SCC 만을 포함하는 Subtree 는 하나 이상 존재한다.

이러한 Subtree 를 찾았다고 해보자. 그러면 이 Subtree 와 나머지 Graph 를 잇는 Edge 를 모두 끊어버릴 수 있다. Subtree 가 빠진 Graph 는 Empty Graph 가 아닌 한 Graph Condensation 시 하나 이상의 Leaf Node 가 새로 생김이 보장된다. 위를 반복하자. 그러면 Graph 내의 SCC 를 모두 구할 수 있다.

그러면 오직 하나의 SCC 만을 포함하는 Subtree(편의상 A)를 어떻게 구할까?

우선 DFS 를 이용해 Spanning Tree 를 만들 때 Node 마다 방문시각을 기록한다. 그러면 A 는 자신을 경유해 Graph 상에서(Spanning Tree 의 Edge 만 사용하는게 아니다.) 도달 가능한 Node 중에 가장 빠른 방문시각을 갖는 Node 를 Root 로 하는 Tree 이다. SCC 내에서는 어디를 시작점으로 잡든 모든 점에 도달할 수 있고, A 는 온전히 SCC 의 Node 만을 가지기 때문에 성립한다.

특징

DFS 의 특성 상 roots[] 의 숫자의 역순으로 SCC 가 위상정렬 되어 있다.