[백준 문제 C++] 2150 Strongly Connected Component

https://www.acmicpc.net/problem/2150

2150번: Strongly Connected Component

 

SCC (Strongly Connected Component) 는 그래프 내에서 사이클을 이루는 각각의 그룹을 의미한다.

연결이 되어 있지 않아 1개인 경우도 하나의 그룹으로 취급한다.

 

문제가 어려워 접근 방법을 몰랐는데

아래 블로그에 SCC에 대해서 [코사라주 알고리즘]과 [타잔 알고리즘]에 대해서 잘 소개해주고 있다.

친절한 설명 덕분에 잘 이해할 수 있게 되었고 직접 실습하고 기억을 남긴다.

https://jason9319.tistory.com/98

SCC(Strongly Connected Component)

 

개념을 간단히 정리해보면 이렇다.

 

[코사라주 알고리즘]

1. 입력에 대한 원본 그래프가 필요하다 (리스트 또는 배열)

2. 역방향 그래프가 필요하다. (입력에 대해서 역방향 ex)  원본이 1 -> 2 라면 2 -> 1로 저장

3. 방문여부 체크용 배열이 필요하다.

4. 스택이 필요하다. <- 이 부분은 벡터로 활용해도 된다. (dfs 함수 재사용을 위해 벡터로 사용해주었다.)

 

step

 1. 원본을 입력 받는다. 동시에 역방향 그래프도 만들어준다.

 2. 원본 그래프에 대한 dfs 를 통해 후위 순회 순서대로 스택에 정점 번호를 저장해준다. (트리의 후위 순회 개념)

 3. 스택에서 정점 번호를 하나씩 꺼내고 방문했는지 확인한다.

   (이미 탐색 o) pass

   (이미 탐색 x) 역방향 그래프로 다시 dfs 를 해본다. 그리고 해당 결과에 이용된 정점들을 저장해준다.

                    이 정점들이 하나의 사이클, 즉 그룹을 이루고 있는 것들이다.

 4. 문제에서 순서대로 출력하는 것을 원하기 때문에 sort를 해준다.

 

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int SIZE = 10001;

bool visited[SIZE];

void dfs(vector<vector<int>> &linkList, vector<int> &subVector, int vertex)
{
	int size = linkList[vertex].size();

	visited[vertex] = true;
	
	for (int i = 0; i < size; ++i)
	{
		int next = linkList[vertex][i];

		if (visited[next])
		{
			continue;
		}

		dfs(linkList, subVector, next);
	}
	
	subVector.push_back(vertex);
}

int main()
{
	vector<vector<int>> link;
	vector<vector<int>> reverseLink;
	vector<vector<int>> group;
	vector<int> arrayStack;
	vector<int> subGroup;

	int v, e;
	int from, to;

	cin.tie(0);
	cin >> v >> e;

	link.resize(v + 1);
	reverseLink.resize(v + 1);

	for (int i = 0; i < e; ++i)
	{
		cin >> from >> to;
	
		link[from].push_back(to);
		reverseLink[to].push_back(from);
	}

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

	memset(visited, false, sizeof(visited));

	for (int i = arrayStack.size() - 1; i >= 0; --i)
	{
		int vertex = arrayStack[i];

		if (visited[vertex])
		{
			continue;
		}

		dfs(reverseLink, subGroup, vertex);
		
		sort(subGroup.begin(), subGroup.end());
		group.push_back(subGroup);
		
		subGroup.clear();
	}

	sort(group.begin(), group.end());
    
	cout << group.size() << endl;
	for (int i = 0; i < group.size(); ++i)
	{
		for (int j = 0; j < group[i].size(); ++j)
		{
			cout << group[i][j] << " ";
		}
		cout << "-1" << endl;
	}
}

 

[타잔 알고리즘]

타잔 알고리즘은 역방향 그래프가 필요없다. 대신에 그룹화가 되어있는지를 체크해줘야 한다.

1. 원본 그래프

2. 방문여부 배열

3. 그룹화여부 배열

4. 스택

 

step

 1. 원본을 입력 받는다.

 

 2. 방문하지 않은 정점부터 SCC 탐색을 시작해준다.

    현재 탐색 순서(ret)와 방문여부(visited)를 지정해준다.

    (이 부분을 통해 나중에 몇 번째부터 그룹화를 해줄지 정해주게 된다.)

    그리고 스택에 현재 방문한 정점을 저장한다.

 

 3. 현재 정점과 연결 된 정점을 찾아본다.

   3-1. 방문했었고 이미 SCC그룹이 확인된 곳)

          그냥 지나친다.

   3-2. 아직 방문하지 않은 곳)  ret = min ( ret, SCC(next) );

          해당 정점을 기준으로 SCC 탐색을 반복한다. 이 때 현재 탐색 순서의 갱신이 필요할 수 있다.

         다음 방문하는 곳에서 그룹의 기준이 될 곳을 만날 수 있기 때문에 현재 탐색 순서 (ret)을 더 작은 값으로

         갱신해줘야 한다.

 

   3-3. 방문했었고, 아직 SCC그룹화 되어있지 않은 곳)  ret = min( ret, visited[next] );

          현재 탐색 순서 (ret)와 해당 탐색 순서 (visited[next])를 비교하여 작은 곳을 기준으로 삼아준다. (ret을 더 작게) 

          이 부분이 어려웠다. 의미하는 것은 아래 그림으로..!

============================================================================

 1번 정점에서 탐색을 시작한다. ret = 1, visited[1] = 1이고 스택에 1을 넣어준다.

 이웃 노드로 미방문 노드 2번이 있다. 이제 SCC(2) 로 간다.

 ret = 2, visited[2] = 2로 시작하고 스택에 2를 넣어준다.

 "-" 는 이미 그룹화가 되어있기 때문에(방문도 되었기에) 더 이상 진행할 필요가 없다. 그냥 넘어가면 된다.

 

 2->1 은 연결이 되어있다. 1번은 이미 지나왔기 때문에 방문 상태이고 그룹화는 되어있지 않다.

1번과 2번은 그룹으로 묶일 수 있게 되는데, 가장 최초의 탐색 순서로 ret을 지정해준다. 이유는 이 ret을 통해

현재 탐색 지점 ~ 최초 탐색 지점 까지 스택에서 꺼내서 그룹으로 묶어주기 위해서이다! ( 스택 { 1 , 2(top) } )

 

 결과적으로 2번의 Ret = 1, Visited[2] = 2가 된다.

============================================================================

 

 4. 현재 Visited와 Ret이 동일한지를 확인한다. 동일하지 않다면 그냥 넘어가면 되고 (ret != visited[index])

   동일하다면 스택에서 현재 번호가 나올때까지 모두 꺼낸다. 이 정점들이 그룹화를 이루고 있는 곳이다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

int order = 1;
bool isScc[10001];
int visited[10001];
vector<vector<int>> list;
vector<vector<int>> group;
stack<int> s;

int SCC(int index)
{ 
	int ret = visited[index] = order++;
	s.push(index);

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

		if (visited[next] == 0)
		{
			ret = min(ret, SCC(next));
		}
		else if (!isScc[next])
		{
			ret = min(ret, visited[next]);
		}
	}

	if (ret == visited[index])
	{
		vector<int> subGroup;
		while (true)
		{
			int vertex = s.top();
			s.pop();

			subGroup.push_back(vertex);
			isScc[vertex] = true;

			if (vertex == index)
			{
				break;
			}
		}

		sort(subGroup.begin(), subGroup.end());
		group.push_back(subGroup);
	}

	return ret;
}

int main()
{
	int v, e, from, to;

	cin.tie(0);
	cin >> v >> e;

	list.resize(v + 1);
	for (int i = 0; i < e; ++i)
	{
		cin >> from >> to;
		list[from].push_back(to);
	}

	for (int i = 1; i <= v; ++i)
	{
		if (visited[i] > 0)
		{
			continue;
		}

		SCC(i);
	}

	sort(group.begin(), group.end());

	cout << group.size() << endl;
	for (int i = 0; i < group.size(); ++i)
	{
		for (int j = 0; j < group[i].size(); ++j)
		{
			cout << group[i][j] << " ";
		}
		cout << "-1" << endl;
	}
}