[AJ/SCC] SCC 문제 및 코드

문제

SCC (Strongly Connected Component)란, 방향성 그래프가 주어질 때 정점을 여러 집합으로 나누는 기법으로써, 같은 집합에 속해있는 정점끼리는 서로 왔다갔다 할 수 있어야 한다. 아래 그림은 그래프의 예제와, 이 그래프에서 SCC를 구한 예제이다.

아래 그림처럼, 정점을 {1, 2, 5}, {6, 7}, {3, 4, 8} 의 3개의 집합으로 나누게 되면, 같은 집합에 속한 정점들끼리는 모두 왔다갔다 할 수 있다. 그래프가 주어질 때, SCC를 구하였을 때 얻을 수 있는 정점의 집합의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. ( 1 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000 ) 둘째 줄부터 간선의 정보가 주어진다. 각 줄은 두 개의 숫자 a, b로 이루어져 있으며, 이는 정점 a에서 정점 b로 향하는 간선이 존재한다는 의미이다. 각 정점의 번호는 1번부터 N번까지이다.

출력

주어진 그래프에서 SCC를 구하였을 때, 얻을 수 있는 정점의 집합의 개수를 출력한다.

예제 입력

8 14 1 5 2 1 2 3 2 6 3 4 3 8 4 3 4 8 5 2 5 6 6 7 7 3 7 6 8 4

예제 출력

3

---

코드

import java.util.Scanner;

public class Main {

	static boolean map[][];
	static boolean reversemap[][];
	static boolean check[], check2[];
	static int n;
	static int order_len = 1;
	static int order[];

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		int m = sc.nextInt();

		map = new boolean[n + 1][n + 1];
		reversemap = new boolean[n + 1][n + 1];
		check = new boolean[n + 1];
		check2 = new boolean[n + 1];
		order = new int[n + 1];

		for (int i = 0; i < m; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			map[a][b] = true;
			reversemap[b][a] = true;
		}

		// 1. DFS를 하면서 빠져나오는 순서대로 시간을 기록한다.
		for (int i = 1; i <= n; i++)
			if (!check[i])
				get_time(i);

		// 2. 뒤집은 그래프에 대해서 빠져나오는 시간이 큰 노드부터 순회한다.
		// 이 때 만나는 노드들은 다 같은 그룹이다.
		int group_cnt = 0;
		for (int i = n; i > 0; i--) {
			int v = order[i];
			if (!check2[v]) {
				get_my_group(v);
				group_cnt++;
			}
		}
		System.out.print(group_cnt);
	}

	static void get_time(int v) {
		check[v] = true;
		for (int i = 1; i <= n; i++)
			if (map[v][i] && !check[i])
				get_time(i);

		order[order_len] = v;
		order_len++;
	}

	static void get_my_group(int v) {
		check2[v] = true;
		for (int i = 1; i <= n; i++) {
			if (reversemap[v][i] && !check2[i])
				get_my_group(i);
		}
	}
  
}