백준 2150 - Strongly Connected Component(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2150

2150번: Strongly Connected Component

강한 연결 요소 알고리즘(SCC)를 사용해 푸는 문제입니다.

문제에서 SCC가 두 개의 정점 u, v에 대해서 u -> v, v -> u로 가는 경로가 모두 존재하는 경우를 의미한다고 알려주지만,
쉽게 말하자면, 그래프의 정점간 순환이 가능한 부분을 의미한다고 생각하면 편합니다.

주어진 그래프를 봤을 때, (a, b, e), (c, d) , (f, g), (h)로 총 4개의 SCC가 존재합니다.
이때 각각의 SCC는 서로 순환이 가능합니다.
하지만 정점 a에서 f로는 갈 수는 있지만 돌아오지는 못합니다. 따라서 a와 f는 같은 SCC에 속하지 않는 것입니다.
이를 바탕으로 SCC는 무방향성이 아닌, 방향성이 있는 그래프에서만 나올 수 있음을 알 수 있습니다.

그렇다면, 이를 구현하는 방법을 알아보겠습니다.
첫번째로 이전에 방문되지 않는 정점을 찾아 해당 정점을 기준으로 SCC를 찾습니다.
해당 정점에서 연결된 정점들이 존재할 것이고, 연결된 정점으로 이동합니다.
이를 반복하다보면, 순환이 되는 그래프인 경우 이전에 방문했던 정점을 방문하게 될 것입니다.
이는 X번 정점 -> ..... -> X번 정점으로 돌아온 것이니 X번 정점부터 방문한 정점들은 모두 SCC가 됩니다.
따라서, 해당 정점들을 같은 SCC로 저장해주면 됩니다. (이는 DFS를 이용함을 알 수 있습니다.)

해당 문제에서 사용한 SCC 알고리즘입니다.

int SCC(int start){ // 주어진 그래프 중, 순환이 가능한 부분을 찾는다.
	int ret = check[start] = vertex++;
	stk.push_back(start);
	for(int i = 0; i < connect[start].size(); i++){
		int next = connect[start][i];
		if(check[next] == -1){
			ret = min(ret, SCC(next));
		}
		else if(SCC_id[next] == -1){
			ret = min(ret, check[next]);
		}
	}
	if(ret == check[start]){
		while(1){
			int x = stk.back();
			SCC_id[x] = SCC_cnt;
			stk.pop_back();
			if(x == start) break;
		}
		SCC_cnt++;
	}
	return ret;
}

코드에서 보면 시작하는 정점(=start)를 시작으로 check 배열을 통해 해당 정점이 몇 번째로 방문하는 점인지를 저장합니다.
start 변수와 연결된 정점들을 확인해서 이전에 방문했던 곳인지를 확인합니다.
->방문하지 않았던 곳이라면 해당 정점으로 이동해 다시 연결된 곳들을 찾습니다.
->방문했던 정점이 나오면, 순환하는 그래프의 가능성이 있다는 의미입니다.
    ->해당 정점이 다른 SCC에 속해있다면, 현재의 SCC에 속하지 않는 것이니 넘어갑니다.
    ->어떤 SCC에도 속해있지 않다면 해당 정점을 방문한 순서와 현재 ret을 비교해 작은 값을 가져옵니다.
이렇게 ret 값을 구했다면, check배열과 ret값이 같은 정점까지 되돌아갑니다.
->이는 해당 정점에서 사이클이 시작되었다는 의미입니다.
따라서 지금까지 방문하면서 저장한 정점들을 해당 정점이 나올 때까지 꺼내고, 같은 SCC로 묶어줍니다.


이를 통해서 SCC를 구했다면, 문제에서 주어진 정렬을 통해 정렬을 한 뒤, 구성 요소들을 출력해주면 됩니다.


자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#define F first
#define S second

using namespace std;

int V, E;
vector<int> connect[10001];
vector<pair<int, int>> Sort; // 해당 SCC 중 가장 작은 값, SCC 번호 

vector<int> stk;
vector<vector<int>> SCC_content; // SCC 안에 들어있는 요소 저장
int check[10001];
int SCC_id[10001];
int SCC_cnt, vertex;

void reset_value(){
	memset(check, -1, sizeof(check));
	memset(SCC_id, -1, sizeof(check));
}

int SCC(int start){ // 주어진 그래프 중, 순환이 가능한 부분을 찾는다.
	int ret = check[start] = vertex++;
	stk.push_back(start);
	for(int i = 0; i < connect[start].size(); i++){
		int next = connect[start][i];
		if(check[next] == -1){
			ret = min(ret, SCC(next));
		}
		else if(SCC_id[next] == -1){
			ret = min(ret, check[next]);
		}
	}
	if(ret == check[start]){
		while(1){
			int x = stk.back();
			SCC_id[x] = SCC_cnt;
			stk.pop_back();
			if(x == start) break;
		}
		SCC_cnt++;
	}
	return ret;
}

bool cmp(pair<int, int> a, pair<int, int> b){
	if(a.F < b.F) return true;
	else return false;
}

void solve(){
	reset_value();
	for(int i = 1; i <= V; i++){
		if(check[i] != -1) continue;
		SCC(i);
	}
	SCC_content.resize(SCC_cnt, vector<int>());
	Sort.resize(SCC_cnt);
	for(int i = 1; i <= V; i++){
		SCC_content[SCC_id[i]].push_back(i);
		if(Sort[SCC_id[i]].F == 0) Sort[SCC_id[i]] = {i, SCC_id[i]};
		else Sort[SCC_id[i]] = {min(i, Sort[SCC_id[i]].F), SCC_id[i]};
	}	
	sort(Sort.begin(), Sort.end(), cmp);
	cout << SCC_cnt << "\n";
	for(int i = 0; i < Sort.size(); i++){
		for(auto &w : SCC_content[Sort[i].S]){
			cout << w << " ";
		}
		cout << "-1" << " " << "\n";
	}
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> V >> E;
	for(int i = 1; i <= E; i++){
		int x, y;
		cin >> x >> y;
		connect[x].push_back(y);
	}	
	solve();
	return 0;
}

 

질문 및 조언은 댓글을 남겨주세요.