강한 결합 요소를 찾는 알고리즘

일단 알고리즘을 설명하기전 강한 결합 요소부터 설명할려 한다. 강한 결합요소 즉, SCC는 그래프에서 하나의 노드에서 시작해 다른 노드까지 갔다가 다시 자신의 노드로 되돌아 올 수 있는 최대 컴포넌트의 모임이다.

이 그래프를 보면 9에서 시작해 (4,5,7)과 (3,6,8) 과 9로 나눌 수 있다는 것을 알 수 있다. 즉, 여기서 SCC는 3개가 나온다.

SCC를 찾는 알고리즘은 2가지가 있다. 그 중 한가지인 코사리주의 알고리즘은 학교 알고리즘 시간에 배웠다. 그 때 교수님께서 다른 방법인 타잔 알고리즘이 있다고 한 것이 기억에 난다. 운이 좋게도 이번 동아리 스터디에서 타잔 알고리즘에 대해 알려줘 공부해 보았다.

 

코사리주 알고리즘

코사리주 알고리즘은 dfs를 2번하여 강한 결합 요소를 찾는 것이다.

첫번째 dfs를 수행해 스택에 더 이상 갈 곳이 없는 노드를 순서대로 삽입한다.

두번째 dfs를 하기 전 그래프를 모두 반대 방향으로 바꾼 뒤 시작 노드를 스택의 top으로 하여 dfs를 한번 더 수행 한다. 이 때 탐색 되는 모든 정점을 SCC로 묶는다. 스택이 비어있을 때까지 반복한다. 만약 top에 위치한 정점이 이미 방문했다면 pop만 한다.

 

타잔 알고리즘 방법

타잔 알고리즘은 DFS를 한번만 수행해 SCC를 찾는 방법이다. 코사리주 알고리즘 보다는 SCC를 찾을 때 적용이 더 쉬워 코딩 테스트에서 자주 사용한다고 한다.

제일 처음 시작 할 노드를 정하고 방문하는 순서에 따라 각 정점에 고유한 id값을 매긴다. 방문 할 때마다 해당 정점을 스택에 삽입한다. 방문할 정점이 여러개이면 사전 순으로 더 낮은 정점부터 방문한다.

위 그래프에서는 9부터 시작한다고 하면 9→5→4→7을 방문하고 각각 1,2,3,4의 id값을 갖는다. 그리고 스택에는 9547이 들어가 있다. 7은 다시 5로 가게된다. 5로 가게 되면 id값은 2로 바뀌고 나머지 4도 id값이 2로 바뀌게 된다. 그 후 5,4,7,이 pop이 된다. 다시 9로가 반대편 8→3→6도 똑같이 수행하고 SCC를 만든 뒤 스택에는 9만 남게 된다. 이렇게 SCC 3개를 만들 수 있다.

 

타잔 알고리즘 구현

vector<int> adj[20202]; //입력 받을 
int d[20202]; //id관리
int f[20202]; //방문했는지 검사
int id; int sccid;
stack<int> st; // dfs돌면서 stack에 삽입
vector<vector<int>> SCC; //SCC 요소 끼리 결합
int sd[20202]; //sccid 관리 

int dfs(int x //현재 노드){
	if(f[x]==true) return -1; //방문 했으면 return;
  d[x]= ++id; //방문한 순서대 id값 입력
	st.push(x);
	int parent = d[x]; 
	for(int y : adx[x]){ // 현재 노드가 갈 수 있는 모든 노드 방문
   if(d[x] == 0) parent = min(parent,dfs(y)); 
   // 현재 노드를 아직 방문 안 했으면 방문 할 요소 중 parent 작은 걸로 초기화
	 else if(!f[y]) parent = min(parent, d[y]); 
   // 방문은 했지만 scc에 안 들어갔으면 현재 노드와 방문했던 것중 parent작은 걸로 초기화
	}
	if(parent == d[x]){ //부모와 자신이 같음 즉 더 이상 방문할 곳 이 없음
	  vector<int> scc;
	  while(true){
	    int t = st.top(); //stack의 top요소부터 고려
	    st.pop();
			sd[t] = sccid; 
		  f[t] = true;
			scc.push_back(t); //scc를 만든다.
		  if(t==x)break;
	  }
    SCC.push_back(scc);
		sccid++;
	}
  return parent;
}

정리

이번에는 타잔 알고리즘에 대해 구현해 보았다. 구현해본 결과 코사리주 알고리즘 보다는 더 빠르게 구현 할 수 있을 것 같다. 이제 이에 관한 백준 문제를 풀어가면서 알고리즘을 익혀야겠다.