강한 연결 요소 (Strongly Connected Components)

  유향 그래프에서 모든 정점이 도달 가능하면 강하게 연결되었다고 한다. 여기서 강한 연결 요소는 부분 그래프의 모든 정점이 강하게 연결된 것이다. 강한 연결 요소를 찾는 것은 O(V + E) 시간에 가능하다.

 

 Transpose graph가 이를 찾는 알고리즘에서 사용되는데, 이는 원래 그래프의 모든 간선의 방향이 반대인 그래프이다.

 

 강한 연결 요소를 찾는 알고리즘은 다음과 같다.

1. DFS를 수행한다.

2. DFS를 수행하고 각각이 끝날 때마다 스택에 집어넣는다.

3. Transpose graph에 대해서 DFS를 수행한다. 이 때 시작점은 스택에서 pop하는 순서대로이다.

4. DFS가 끝날 때마다 저장한다.

 

이를 C++로 구현하면 다음과 같다.

int v, e;
vector<int> edges[10001];
vector<int> transpose[10001];
vector<bool> visited;
stack<int> st;
vector<int> tempNodes;
vector<vector<int>> answer;

void dfs(int start)
{
	visited[start] = true;

	for (int i = 0; i < edges[start].size(); i++)
	{
		int next = edges[start][i];

		if (!visited[next])
		{
			dfs(next);
		}
	}

	st.push(start);
}

void transDfs(int start)
{
	visited[start] = true;

	for (int i = 0; i < transpose[start].size(); i++)
	{
		int next = transpose[start][i];

		if (!visited[next])
		{
			transDfs(next);
		}
	}

	tempNodes.push_back(start);
}

int main()
{
	visited = vector<bool>(v + 1, false);

	for (int i = 1; i <= v; i++)
	{
		if (!visited[i])
		{
			dfs(i);
		}
	}

	visited = vector<bool>(v + 1, false);

	while (!st.empty())
	{
		int present = st.top();
		st.pop();

		if (!visited[present])
		{
			tempNodes = vector<int>();
			transDfs(present);
			answer.push_back(tempNodes);
		}
	}	
}