[백준]: 2150번: Strongly Connected Component / 코사리주 알고리즘

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

해당문제를 풀기위해서는 강한결합요소의 개념을 알아야한다. 

간략한 설명 

1. DFS수행전에 유향그래프(Graph)와 역방향유향그래프(Reverse_Graph)를 미리 세팅해놓는다.

2. DFS를 수행한다. 끝난 순서대로 Stack에 담는다.

3. Stack에서 pop을 하면서 역방향유향그래프에 대해서 DFS를 수행한다. dfs가 가능한 정점끼리는 vector로 묶는다.

배열로도 SCC를 구할수 있지만, SCC그룹내의 여러개가 존재시 가장 작은 정점의 번호순으로 출력해야함으로 vector와 pair의 조합으로 해결할 수 있음. 

#include <iostream>

#include <cstring>

#include <queue>

#include <vector>

#include <stack>

#include <algorithm>

using namespace std;

int indexSCC; bool visited[10001]; 

stack<int> Stack;

void dfs(vector<vector<int>> &adj, int startNode)

{

visited[startNode] = true;

for (int i = 0; i < adj[startNode].size(); i++)

if (!visited[adj[startNode][i]]) dfs(adj, adj[startNode][i]);

Stack.push(startNode);

}

void Kosaraju(vector<vector<int>> &rev_adj, int startNode, vector<int> &SCC)

{

visited[startNode] = true;

SCC.push_back(startNode);

for (int i = 0; i < rev_adj[startNode].size(); i++)

if (!visited[rev_adj[startNode][i]]) Kosaraju(rev_adj, rev_adj[startNode][i], SCC);

}

int main()

{

int N, T, A, B;

vector<vector<int>> adj, rev_adj, SCC;

cin >> N >> T;

adj.resize(N + 1); rev_adj.resize(N + 1);

while (cin >> A >> B) adj[A].push_back(B), rev_adj[B].push_back(A);

for (int i = 1; i <= N; i++) if (!visited[i]) dfs(adj, i);

memset(visited, 0, sizeof(visited));

while (!Stack.empty())

{

int top = Stack.top();

Stack.pop();

if (visited[top]) continue;

SCC.resize(++indexSCC);

Kosaraju(rev_adj, top, SCC[indexSCC - 1]);

}

cout << indexSCC << '\n';

for (int i = 0; i < indexSCC; i++) sort(SCC[i].begin(), SCC[i].end());

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

for (int i = 0; i < indexSCC; i++)

{

for (int j = 0; j < SCC[i].size(); j++) cout << SCC[i][j] << ' ';

cout << -1 << '\n';

}

return 0;

}