[백준 온라인 저지] 2150. Strongly Connected Component

방향 그래프가 주어졌을 때, 그 그래프를 SCC들로 나누는 프로그램을 작성하시오.

 

1. 입력

- 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다.

- 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이다. 이때 방향은 A → B가 된다.

- 정점은 1부터 V까지 번호가 매겨져 있다.

 

2. 출력

- 첫째 줄에 SCC의 개수 K를 출력한다.

- 다음 K개의 줄에는 각 줄에 하나의 SCC에 속한 정점의 번호를 출력한다. 각 줄의 끝에는 -1을 출력하여 그 줄의 끝을 나타낸다. 각각의 SCC를 출력할 때 그 안에 속한 정점들은 오름차순으로 출력한다. 또한 여러 개의 SCC에 대해서는 그 안에 속해있는 가장 작은 정점의 정점 번호 순으로 출력한다.

 

3. 예제

 

4. 코드

import java.util.*;
import java.io.*;
class Main {
    static int v, e; // 주어진 그래프의 정점, 간선의 개수
    static int[] parent; // 부모 노드의 번호
    static List<List<Integer>> scc = new ArrayList<List<Integer>>(); // SCC
    static List<List<Integer>> edges = new ArrayList<List<Integer>>(); // 노드별 간선 정보
    static Stack<Integer> stack = new Stack<>(); // dfs 수행 시 이용할 스택
    static int id = 0; // 노드 방문시 붙여줄 고유번호. 1번부터 매긴다.
    static boolean[] finished; // 처리가 완료됐다면 true
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer token = new StringTokenizer(br.readLine());
        v = Integer.valueOf(token.nextToken()); e = Integer.valueOf(token.nextToken());
        parent = new int[v+1]; finished = new boolean[v+1];
        for(int i=0 ; i<=v ; i++) // i번 노드와 연결된 노드를 담는다.
            edges.add(new ArrayList<>());
        for(int i=1 ; i<=e ; i++){
            token = new StringTokenizer(br.readLine());
            edges.get(Integer.valueOf(token.nextToken())).add(Integer.valueOf(token.nextToken()));
        }
        for(int i=1 ; i<=v; i++) // 각 노드를 방문하며 dfs 수행
            if(parent[i]==0) dfs(i);
        bw.write(scc.size()+"\n");
        for(int i=0 ; i<scc.size(); i++)
        	scc.get(i).sort(Comparator.naturalOrder());
        scc.sort(new Comparator<>() {
        	@Override
        	public int compare(List<Integer> l1, List<Integer> l2) {
        		return l1.get(0).compareTo(l2.get(0));
        	}
        });
        for(int i=0 ; i<scc.size(); i++) {
            for(int j=0 ; j<scc.get(i).size(); j++)
                bw.write(scc.get(i).get(j)+" ");
            bw.write("-1\n");
        }
        bw.flush(); bw.close();
    }
    
    static int dfs(int n) {
        parent[n] = ++id; // 수행되는 순서대로 노드에 고유 번호를 매긴다.
        stack.push(n); // 스택에 노드 삽입
        int p = parent[n];
        for(int x : edges.get(n)) {
            if(parent[x]==0) // x가 방문하지 않았던 노드인 경우
                p = Math.min(p, dfs(x));
            else if(!finished[x]) // 방문은 했으나 스택에 있는 경우
                p = Math.min(p, parent[x]);
        }

        if(p==parent[n]) { // 자기 자신이 부모라는 것을 알았을 경우
            List<Integer> list = new ArrayList<>();
            while(true) {
                int x = stack.pop(); // 스택에서 노드를 꺼낸 후
                list.add(x);  // 리스트에 넣고
                finished[x] = true; // 처리 완료 작업을 한다.
                if(x==n) break; // 자기 자신에 도달하면 리스트 작성을 중단한다.
            }
            scc.add(list); // 작성한 리스트를 scc에 저장한다.
        }
        return p;
    }
}

- 51148KB, 616ms