22_5_SCC.md

22.5 Strongly connected component

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

Kosaraju's algorithm

실제 책에 소개되는 알고리즘

참고 : https://jason9319.tistory.com/98

$O(V+E)$

Graph STRONGLY_CONNECTED_COMPONENTS(const Graph &G)
{
	const int v = G.size()-1;
	 
	Graph SSC;
	std::stack<int> DFSf; // DFS pop 순서대로 들어가있다.
	std::vector<bool> visit(v+2 ,false);
	for (int i = 1; i <= v; i++) {
		if (visit[i] != true)
			DFS(G, i, DFSf,visit); //DFS순회 순서를 S에 저장한다.
	}

	Graph TG(v + 1, (std::vector<int>()));//G^T
	for (int i = 1; i <= v; i++)
	{
		for (int j : G[i])
		{
			TG[j].push_back(i);
		}
	}
	
	visit.assign(v+1,false);
	for (int i = 0; i < v; i++)
	{
		if (visit[DFSf.top()] != true)
		{
			SSC.push_back(std::vector<int>());
			TDFS(TG, DFSf.top(), SSC[SSC.size()-1],visit);
			///SSC_n++;
		}
		DFSf.pop();
	}
	return SSC;
}

with for

void DFS(const Graph &G, int x, std::stack<int>& DFSf , std::vector<bool> &visit)
{
	visit[x] = true;
	std::stack<int> sub_s;
	sub_s.push(x);
	while (!sub_s.empty())
	{
		int y = sub_s.top();
		for (std::size_t i = 0; i < G[y].size(); i++)
		{
			int next = G[y][i];
			if (visit[next] != true)
			{
				visit[next] = true;
				sub_s.push(next);
				i = -1;
				y = sub_s.top();
			}
		}
		DFSf.push(sub_s.top());//기존 DFS와 차이 STACK에 종료 순서 저장
		sub_s.pop();
	}
}

with recursion

void DFS(const Graph& G, int x, std::stack<int>& DFSf, std::vector<bool>& visit)
{
	visit[x] = true;

	//std::cout << x << ' '; // 순회출력

	for (int next : G[x])
	{
		if (visit[next] != true)
		{
			DFS(G, next, DFSf,visit);
		}
	}
	DFSf.push(x);//기존 DFS와 차이 STACK에 종료 순서 저장
}

with for

void TDFS(Graph &TG, int x,std::vector<int> &SSC, std::vector<bool> &visit)//G^T탐색
{
	visit[x] = true;

	std::stack<int> sub_s;
	sub_s.push(x);

	//std::cout << sub_s.top() << ' '; // 순회출력

	while (!sub_s.empty())
	{
		int y = sub_s.top();
		for (std::size_t i = 0; i < TG[y].size(); i++)
		{
			int next = TG[y][i];
			if (visit[next] != true)
			{
				visit[next] = true;
				sub_s.push(next);
				
				//std::cout << sub_s.top() << ' '; // 순회출력
			
				i = -1;
				y = sub_s.top();
			}

		}
		SSC.push_back(sub_s.top());
		sub_s.pop();
	}
}

with recursion

//SSC[] 1D vector
void TDFS(Graph& TG, int x, std::vector<int>& SSC, std::vector<bool>& visit)
{
	visit[x] = true;
	//std::cout << x << ' '; // 순회출력
	for (int next : TG[x])
	{
		if (visit[next] != true)
		{
			TDFS(TG, next, SSC,visit);
		}
	}
	SSC.push_back(x);
}

+ Tarjan's alg

$O(V+E)$

참고 : https://blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221236952158&parentCategoryNo=&categoryNo=128&viewDate=&isShowPopularPosts=false&from=postView

해당 코드를 토대로 매개변수를 옮김

// 자신의 결과값을 리턴하는 DFS 함수
int DFS(int curr, vector<vector<int>>& SCC,
	vector<bool>& finished, stack<int>& S, vector<vector<int>>& adj, vector<int>& dfsn, int &cnt)
{
	dfsn[curr] = ++cnt; // dfsn 결정
	S.push(curr);       // 스택에 자신을 push

	// 자신의 dfsn, 자식들의 결과나 dfsn 중 가장 작은 번호를 result에 저장
	int result = dfsn[curr];
	for (int next : adj[curr])
	{
		// 아직 방문하지 않은 이웃
		if (dfsn[next] == 0)
		{
			result = min(result, DFS(next, SCC, finished, S, adj, dfsn, cnt));
		}
		// 방문은 했으나 아직 SCC로 추출되지는 않은 이웃
		else if (!finished[next])
		{
			result = min(result, dfsn[next]);
		}
	}

	// 자신, 자신의 자손들이 도달 가능한 제일 높은 정점이 자신일 경우 SCC 추출
	if (result == dfsn[curr])
	{
		vector<int> currSCC;
		// 스택에서 자신이 나올 때까지 pop
		while (1)
		{
			int t = S.top();
			S.pop();
			currSCC.push_back(t);
			finished[t] = true;
			//sn[t] = SN;
			if (t == curr)
			{
				break;
			}
		}
		// 출력을 위해 원소 정렬
		sort(currSCC.begin(), currSCC.end());
		// SCC 추출
		SCC.push_back(currSCC);
	}
	return result;
}

std::vector<vector<int>> TARJAN_ALG(std::vector<vector<int>>& adj)
{
	const int V = adj.size();

	std::vector<int>  dfsn(V + 1);
	std::vector<vector<int>> SCC;
	std::stack<int> S;
	std::vector<bool> finished(V + 1); // SCC 분리가 끝난 정점만 true
    int cnt = 0 ;

	for (int i = 0; i < V - 1 ; i++)
	{
		if (dfsn[i] == 0)
		{
			DFS(i, SCC, finished, S, adj, dfsn,cnt);
		}
	}
	return SCC;
}