Strongly Connected Component 강한 결합 요소

#include <iostream>
#include <vector>
#include <stack>
#define N 10001

using namespace std;

int d[N]; //dfs을 했는가 안했는가 및, 노드에 몇번 째로 dfs를 진입했는지를 나타냄
int id=0;
vector<int> a[N]; //그래프의 간선을 담는 배열 
vector<vector<int> > SCC; //강한 결합 요소
//이중 벡터인 이유 : 그래프에서 강한 결합 요소가 여러개 있을 수 있다.
//그래서, 그 요소들을 하나의 백터로 보고, 이 요소(백터)들을 한꺼번에 넣는 것이
//SCC이다.

stack<int> s; //강한 결합 요소를 알기 위해 사용하는 stack
bool finished[N] = {}; //stack에서 나왔다면 1, 아니라면 0 

int dfs(int x) {
	d[x] = ++id;
    s.push(x); //dfs한 것을 스택에다가 넣기
	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));
		else if(!finished[y]) parent = min(parent, d[y]);
	} 
	
	if(parent == d[x]) {  //자기자신이 부모노드일 경우 강한 연결 요소 만들기 
		while(1) { //stack 비우기 -> scc만들기 
			vector<int> scc;
			int t = s.top();
			s.pop();
			scc.push_back(t);
			finished[t] = true;
			if(x==t) break;
		}
		SCC.push_back(scc); //SCC에 저장 
	}
	return parent;
}

int main(void)
{
	int n, m;
	for(int i=1; i<=n; i++) if(d[i] == 0) dfs(i);
	
	for(int i=0; i<SCC.size(); i++) {
		for(int j=0; j<SCC[i].size(); j++)
	}
}

 

사용하는 것 : stack, vector, dfs

 

사용하는 변수 및 배열

int d[]; //dfs함수에 들어가지 않았으면 0, 들어갔으면 1

int id; //dfs의 순서, dfs에 들어온 노드에 번호를 마킹한다.

 

vector<int> a[] //그래프의 간선을 넣는다.

vector<vector<int> > SCC //강한 결합 요소를 만든 상태에서의 그래프를 저장한다. 강한 결합 요소 하나하나가 vector로 이루어져 있기에, 이중벡터로 만든 다음 벡터들을 저장하게 한다.

 

stack<int> s //dfs을 한것을 넣는 공간이다. 또한 부모노드가 자기자신임이 결정되면, stack에 있는 것을 하나의 scc(강한 결합 요소)로 만든다. 이를 SCC에 저장한다.

bool finished[] //bool로 한 이유는 0, 1만 있는 타입이다. 0 : stack에서 나오지 않았을 때, 1 : stack에서 나왔을 때

//이 배열이 있는 이유는, stack에서 나오기 전까지는 누가 부모인지는 정해지지 않았기 때문이며, stack에서 나온 이상

//건드려선 안되기 때문이다. 또한 이미 dfs를 했으나(더 이상 dfs을 못하므로) , scc가 되지 않았다면, 아직 부모가 바뀔수 있는 경우가 있으니 만들어 놓은 장치이다.