[BOJ] 2150 - Strongly Connected Component

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

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

2150번: Strongly Connected Component

난이도: 플래티넘 5

사용언어: JAVA

 

풀이

 

이름 그대로 Strongly Connected Component(SCC) 문제의 가장 기본적인 유형입니다. 저는 코사라주 알고리즘을 이용하여 문제를 해결하였습니다. 코사라주 알고리즘은 아래의 링크에서 더 자세하게 확인하실 수 있습니다.

 

https://jooona.tistory.com/159

[알고리즘] 코사라주 알고리즘

 

 

import java.io.*;
import java.util.*;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static ArrayList<ArrayList<Integer>> conn = new ArrayList<>(); // 순방향 그래프
    static ArrayList<ArrayList<Integer>> reconn = new ArrayList<>(); // 역방향 그래프
    static boolean[] visit; // 방문 여부 확인
    static int[] scc; // 어떤 노드들이 하나의 SCC로 묶였는지를 표시하기 위한 배열
    static Stack<Integer> stack = new Stack<>(); // 스택
 
    static int N, M;
 
    public static void dfs(int node) { // 순방향 그래프에 대한 dfs
        visit[node] = true; // 방문했다고 체크
 
        for (int i = 0; i < conn.get(node).size(); i++) {
            int next = conn.get(node).get(i); // 다음 탐색할 노드 선정
 
            if (visit[next] == false) { // 아직 방문하지 않은 노드라면
                dfs(next); // 순방향 그래프에 대한 dfs 진행
            }
        }
        stack.push(node); // 탐색이 끝난 노드는 스택에 push
    }
 
    public static void redfs(int node, int number) { // 역방향 그래프에 대한 dfs.
                                                     // node: 현재 탐색 중인 node, number: 현재 scc 번호
        visit[node] = true; // 방문했다고 체크
        scc[node] = number; // 탐색되는 노드는 현재 scc에 포함
 
        for (int i = 0; i < reconn.get(node).size(); i++) {
            int next = reconn.get(node).get(i); // 다음 탐색할 노드 선정
            if (visit[next] == false) { // 아직 방문하지 않은 노드라면
                redfs(next, number); // 역방향 그래프에 대한 dfs 진행
            }
        }
    }
 
    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        visit = new boolean[N + 1];
        scc = new int[N + 1];
 
        for (int i = 0; i < N + 1; i++) {
            conn.add(new ArrayList<>());
            reconn.add(new ArrayList<>());
        }
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
 
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
 
            conn.get(n).add(m);
            reconn.get(m).add(n);
        }
 
        for (int i = 1; i < N + 1; i++) { // 모든 정점에 대하여
            if (visit[i] == false) { // 방문한 노드를 제외하고
                dfs(i); // 순방향 그래프에 대한 dfs 실행
            }
        }
 
        Arrays.fill(visit, false); // 방문 여부를 체크할 visit 배열 초기화
 
        int num = 1;
        while (!stack.isEmpty()) { // 스택이 빌 때 까지
            int node = stack.pop();
 
            if (visit[node] == false) { // 이미 방문한 노드가 아니면
                redfs(node, num++); // 역방향 그래프에 대한 dfs 실행
            }
        }
 
        HashSet<Integer> hs = new HashSet<>(); // HashSet을 이용하여 몇 개의 scc가 존재하는지 파악
        for (int i = 1; i <= N; i++) {
            hs.add(scc[i]);
        }
        bw.write(String.valueOf(hs.size()) + "\n"); // scc의 갯수 출력
 
        Arrays.fill(visit, false);
        for (int i = 1; i <= N; i++) { // 각각의 scc에 속하는 노드들을 출력
            
            if (visit[i] == false) {
                int tmp = scc[i];
                visit[i] = true;
                bw.write(String.valueOf(i) + " ");
                for (int j = 1; j <= N; j++) {
                    if (i == j)
                        continue;
 
                    if (tmp == scc[j]) {
                        bw.write(String.valueOf(j) + " ");
                        visit[j] = true;
                    }
                }
                bw.write("-1\n");
            }
        }
 
        bw.flush();
        bw.close();
        br.close();
    }
}