[기본문제풀이] 강한결합요소

 

풀이 일시 : 2020-08-17

​

강한결합요소 :

strongly connected component SCC로 부르기도 한다.

같은 SCC에 속하는 두 정점은 서로 도달이 가능하다.

​

문제 :

SCC의 갯수와 각 SCC에 담긴 인자들을 출력하라

​

풀이 :

모든 정점에 대해 DFS를 수행해서 SCC를 찾는 알고리즘으로 풀이한다.

1->2->3->4 에서 다시 1로 돌아갈 수 있어야 SCC가 성립하는 것.

​

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

int id, d[MAX];
bool finished[MAX]; //특정한 dfs가 끝났는지 확인하기위해
vector <int> a[MAX];
vector<vector<int> >SCC;
stack<int> s;

int dfs(int x) {
	d[x] = ++id; //노드마다 고유한 번호를 할당 / 방문표시, 다시 dfs실행안하기위함
	s.push(x); //스택에 자기 자신을 삽입

	int parent = d[x]; //자신의 부모가 누구인지 확인할수있게
	for (int i = 0; i < a[x].size(); i++) { //인접한 노드를 방문
		int y = a[x][i];
		//방문하지않은 이웃
		if (d[y] == 0) parent = min(parent, dfs(y)); //해당노드를 방문한적없다면 해당노드로 dfs를 수행하여 더 작은값으로 부모값갱신
		//처리되지 않은 이웃
		else if (!finished[y]) parent = min(parent, d[y]); //방문은했지만 처리가안됐으면 (dfs수행노드) 더 작은값으로
	}
	if (parent == d[x]) { //부모노드가 자기자신인 경우
		vector<int> scc; //스택에서 꺼내면서 scc를 만들어준다.
		while (1) {
			int t = s.top();
			s.pop();
			scc.push_back(t);
			finished[t] = true;
			if (t == x) break; //자기자신이 나올때까지 스택에서 뽑아준다.
		}
		SCC.push_back(scc);
	}
	return parent;
}

int main() {
	int v = 11;
	a[1].push_back(2);
	a[2].push_back(3);
	a[3].push_back(1);
	a[4].push_back(2);
	a[4].push_back(5);
	a[5].push_back(7);
	a[6].push_back(5);
	a[7].push_back(6);
	a[8].push_back(5);
	a[8].push_back(9);
	a[9].push_back(10);
	a[10].push_back(11);
	a[11].push_back(3);
	a[11].push_back(8);

	for (int i = 1; i <= v; i++) {
		if (d[i] == 0) dfs(i); //각 정점에 대해 한번씩 dfs실행
	}

	printf("SCC의 갯수: %d\n", SCC.size());
	for (int i = 0; i < SCC.size(); i++) {
		printf("%d번째 SCC: ", i + 1);
		for (int j = 0; j < SCC[i].size(); j++) {
			printf("%d ", SCC[i][j]);
		}
		printf("\n");
	}
	return 0;
}