[BOJ] 백준 [4196] 도미노 JAVA

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

4196번: 도미노

[문제]

[풀이]

x => y => ... 로 가는 간선이 있을 때 , x 를 넘어뜨리면 이와 연결된 모든 도미노가 넘어간다.
즉 , inDegree 가 0인 부분을 선택해서 카운팅 해줘야 하는 문제이다.

그런데 만약 사이클이 있는 경우는 inDegree를 정의하기가 어렵기 때문에 사이클이 있는부분은
어느 하나만 건드리면 나머지도 다 넘어지기 때문에 이 사이클을 하나의 노드로 봐야 한다.

그래서 SCC (강한 결합 요소) 알고리즘중 하나인 타잔 알고리즘을 사용.
SCC로 묶인 노드들을 하나의 노드로 보고 , 이 SCC 끼리의 위상정렬을 이용해서 inDegree가 0인것을 찾으면 끝. 

import java.util.*;
import java.io.*;
import java.util.stream.*;
 
public class Main {
    static boolean[] finished;
    static int n,m,index,sccIndex;
    static int[] discover,inDegree,sccNum;
    static ArrayList<ArrayList<Integer>> list;
    static Stack<Integer> st;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        while (tc-->0){
            String[] input = br.readLine().split(" ");
            n = Integer.parseInt(input[0]);
            m = Integer.parseInt(input[1]);
            list = new ArrayList<>();
 
            for(int i=0;i<=n;i++) list.add(new ArrayList<>());
 
            for(int i=0;i<m;i++){
                int[] edge = Arrays.stream(br.readLine().split(" "))
                        .mapToInt(Integer::parseInt).toArray();
                list.get(edge[0]).add(edge[1]);
            }
 
            findScc();
            setInDegree();
            System.out.println(getZeroInDegree());
 
        }
    }
 
    private static int getZeroInDegree() {
        int ans=0;
        for(int i=1;i<=sccIndex;i++)
            if(inDegree[i]==0) ans++;
            return ans;
    }
 
    private static void setInDegree() {
        inDegree = new int[sccIndex+1];
 
        for(int i=1;i<=n;i++)
            for (Integer next : list.get(i))
                if(sccNum[i] != sccNum[next]) inDegree[sccNum[next]]++;
    }
 
    private static void findScc() {
 
        index=0;
        discover = new int[n+1];
        finished = new boolean[n+1];
        st = new Stack<>();
        sccIndex = 0;
        sccNum = new int[n+1];
 
        for(int i=1;i<=n;i++)
            if(discover[i]==0) dfs(i);
 
    }
 
    private static int dfs(int cur) {
        discover[cur] = ++index;
        st.push(cur);
 
        int parent = discover[cur];
        for (Integer next : list.get(cur)) {
            if(discover[next]==0) parent = Math.min(dfs(next),parent);
            else if(!finished[next]) parent = Math.min(discover[next],parent);
        }
 
        if(parent==discover[cur]){
            while (true){
                Integer pop = st.pop();
                finished[pop]=true;
                sccNum[pop] = sccIndex+1;
                if(pop==cur) break;
            }
            sccIndex++;
        }
        return parent;
    }
}