강한 연결 요소

 

정의

방향 그래프에서, 모든 정점들이 서로 도달 가능한 최대 부분 그래프

⇒ SCC 내 임의의 정점 $u,v$에 대해, $u \rightarrow v$경로와 $v \rightarrow u$경로가 모두 존재

특성

• 모든 방향 그래프는 하나 이상의 SCC로 분해될 수 있음
• SCC들은 서로 겹치지 않음 (SCC 정의가 최대 부분 그래프이기 때문)
• 모든 정점은 정확히 하나의 SCC에 속함
• 방향 그래프의 SCC들을 하나의 정점으로 압축하면 DAG가 됨.

SCC 찾기

코사라주 알고리즘

1. 각 정점에 DFS Finishing Time을 기록
2. Finishing Time ⇒ 오일러 경로 테크닉에서 out time의 개념과 동일함
3. 모든 간선의 방향을 뒤집은 전치 그래프에서, 탐색 종료의 역순으로 정점을 방문하여 생긴 DFS 트리가 하나의 SCC가 됨

---

구현해보자.

1. 정방향, 역방향 그래프 $G, R$을 준비한다.
2. Finishing Time의 역순을 구하는 대신, 탐색을 마칠 때 Stack에 정점을 넣어주는 방식을 채택
3. Stack에서 하나씩 꺼내며 SCC 추출

타잔 알고리즘

1. 각 정점에 DFS Discovery Time과 low-link값을 기록low-link ⇒ 도달 가능한 정점의 Discovery Time 중 최솟값
2. Discovery Time ⇒ 오일러 경로 테크닉에서 in time의 개념과 동일함

코드

https://www.acmicpc.net/problem/2150 AC 코드

import java.util.*;
import java.io.*;

public class Main {
	
	// IO field
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st = new StringTokenizer("");

	static void nextLine() throws Exception {st = new StringTokenizer(br.readLine());}
	static String nextToken() throws Exception {
		while(!st.hasMoreTokens()) nextLine();
		return st.nextToken();
	}
	static int nextInt() throws Exception { return Integer.parseInt(nextToken()); }
	static long nextLong() throws Exception { return Long.parseLong(nextToken()); }
	static double nextDouble() throws Exception { return Double.parseDouble(nextToken()); }
	static void bwEnd() throws Exception {bw.flush();bw.close();}
	
	// Additional field
	
	static int V, E;
	static List<Integer>[] G, R;
	static Stack<Integer> S;
	static boolean[] vis;
	static int ord = 0;
	
	public static void main(String[] args) throws Exception {
		
		ready();
		solve();
		
		bwEnd();
		
	}
	
	static void ready() throws Exception{
		
		V = nextInt();
		E = nextInt();
		G = new List[V+1];
		R = new List[V+1];
		S = new Stack<>();
		vis = new boolean[V+1];
		for(int i=1;i<=V;i++) {
			G[i] = new ArrayList<>();
			R[i] = new ArrayList<>();
		}
		for(int i=0;i<E;i++) {
			int a = nextInt(), b = nextInt();
			G[a].add(b);
			R[b].add(a);
		}
		
	}
	
	static void solve() throws Exception {
		
		for(int i=1;i<=V;i++) if(!vis[i]) {
			vis[i] = true;
			dfs1(i);
		}
		
		vis = new boolean[V+1];
		List<List<Integer>> ans = new ArrayList<>();
		while(!S.isEmpty()) {
			int n = S.pop();
			if(vis[n]) continue;
			vis[n] = true;
			List<Integer> res = new ArrayList<>();
			dfs2(n, res);
			Collections.sort(res);
			ans.add(res);
		}
		Collections.sort(ans, (a,b) -> a.get(0).compareTo(b.get(0)));
		
		bw.write(ans.size() + "\n");
		for(List<Integer> res:ans) {
			for(int i:res) bw.write(i + " ");
			bw.write("-1\n");
		}
		
	}
	
	static void dfs1(int n) {
		ord++;
		for(int i:G[n]) if(!vis[i]) {
			vis[i] = true;
			dfs1(i);
		}
		S.add(n);
	}
	
	static void dfs2(int n, List<Integer> L) {
		L.add(n);
		for(int i:R[n]) if(!vis[i]) {
			vis[i] = true;
			dfs2(i, L);
		}
	}
	
}