강한 결합 요소 SCC(Strong connected component)

// SCC strong connected component
// 방향 그래프일때만 고려가능하다
// 사이클이 발생하는 경우 무조건 SCC에 해당한다
// 타잔(tarjan)알고리즘
// 모든 정점에 대해서 DFS를 수행해서 SCC를 찾는다
// 한 정점에서 출발해서 다시 출발 정점으로 돌아올 수 있는 경로에 한해서 SCC가 존재한다

// DFS 중에 발견한 정점이 스택내에 들어가있다면 이 정점이 나의 부모정점이다 라는 의미가 된다
// 이때부터 리턴을 하다가 자기 자신과 부모가 같은 정점으로 되돌아오면 출발 정점이 됨을 의미한다
// 부모값이 자신보다 더 작은 값으로 갱신되면서 부모정점으로 되돌아가게 되는 탐색

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

bool finished[MAX]; // 현재 특정한 노드에 대한 DFS가 끝났는지 확인
int id, d[MAX]; // id : 각 노드마다 고유한 번호를 할당할 변수, d : 정점마다 할당된 번호를 담기 위함
vector<int> a[MAX];
vector<vector<int> > SCC;
stack<int> s;

// DFS는 총 정점의 갯수만큼 실행
int dfs(int x) {
	d[x] = ++id; // 노드마다 고유한 번호를 할당 (맨처음 부모로 설정된 값)
	s.push(x);

	int parent = d[x]; // 초기에는 id 자체를 고유 번호로 지정

	for (int i = 0; i < a[x].size(); i++) {
		int y = a[x][i]; // x와 연결된 정점 y

		// ** 더 작은 값으로 부모를 가리키도록 탐색한다 **

		// 해당노드를 방문한 적이 없다면 dfs를 수행
		if (d[y] == 0) parent = min(parent, dfs(y));
		// 방문은 했는데 처리가 끝나지 않은 정점이라면
		else if (!finished[y]) parent = min(parent, d[y]);
	}
	
	// 부모노드가 자기 자신인 경우
	if (parent == d[x]) {
		// 스택에서 자기자신이 나올떄까지 뽑아서 SCC에 저장
		vector<int> 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 N; // N is node_cnt

	// for dfs i 1 to N
	for (int i = 1; i <= N; i++) {
		// check ths not visit node
		if (d[i] == 0) dfs(i);
	}

}