[BOJ] 백준 [2150] 강한 결합 요소 JAVA

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

2150번: Strongly Connected Component

문제

풀이

SCC (강한 결합 요소)를 구하기위해 코사라주 알고리즘을 사용했다.

1. 그래프를 dfs 로 탐색하면서 Stack에 탐색한 정점들을 push

2. Stack 에서 원소 하나씩 Pop 하면서 , 역방향 그래프 탐색

 

 

import java.util.*;
import java.io.*;
 
public class Main{
    static int V,E;
    static boolean[] visit;
    static ArrayList<Integer>[] list;
    static ArrayList<Integer>[] listReverse;
    static Stack<Integer> st;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        V = input[0]; E = input[1];
        init();
        for(int i=0;i<E;i++){
            input = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt).toArray();
            list[input[0]].add(input[1]);
            listReverse[input[1]].add(input[0]);
        }
 
        for(int i=1;i<=V;i++)
            if(!visit[i]) dfs(i);
 
        visit = new boolean[V+1];
        int ret=0;
        list = new ArrayList[V+1];
        for(int i=1;i<=V;i++) list[i] = new ArrayList<>();
        while(!st.isEmpty()){
            Integer pop = st.pop();
            if(!visit[pop]) reverseDfs(pop,++ret);
        }
 
        TreeMap<Integer, ArrayList<Integer>> map = new TreeMap<>();
 
 
 
        for(int i=1;i<=ret;i++){
            list[i].sort(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1-o2;
                }
            });
            map.put(list[i].get(0),list[i]);
        }
        System.out.println(ret);
 
        map.entrySet().iterator().forEachRemaining(e->{
            e.getValue().forEach(l-> System.out.print(l+" "));
            System.out.println("-1");
        });
 
    }
 
    static void init() {
        list = new ArrayList[V+1];
        listReverse = new ArrayList[V+1];
        visit = new boolean[V+1];
        for(int i=1;i<=V;i++) list[i] = new ArrayList<>();
        for(int i=1;i<=V;i++) listReverse[i] = new ArrayList<>();
        st = new Stack<>();
    }
    static void dfs(int cur){
        visit[cur] = true;
 
        for (Integer next : list[cur]) {
            if(!visit[next]) dfs(next);
        }
        st.push(cur);
    }
 
    static void reverseDfs(int cur,int cnt){
        visit[cur] = true;
 
        for (Integer next : listReverse[cur]) {
            if(visit[next]) continue;
            reverseDfs(next,cnt);
        }
        list[cnt].add(cur);
    }
}

 

풀이2 ( 타잔 알고리즘)

 

import java.util.*;
import java.io.*;
 
public class Main{
    static int V,E,index;
    static ArrayList<ArrayList<Integer>> SCC;
    static ArrayList<Integer>[] list;
    static Stack<Integer> st;
    static boolean[] finish;
    static int[] parent;
    static int[] discover;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        V = input[0]; E = input[1];
        init();
        for(int i=0;i<E;i++){
            input = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt).toArray();
            list[input[0]].add(input[1]);
 
        }
        for(int i=1;i<=V;i++) {
            if (discover[i]==0) dfs(i);
        }
        System.out.println(SCC.size());
 
        for (ArrayList<Integer> e : SCC) e.sort(((o1, o2) -> o1-o2));
        SCC.sort((o1, o2) -> o1.get(0)-o2.get(0));
 
        for (ArrayList<Integer> sccList : SCC) {
            sccList.forEach(e->System.out.print(e+" "));
            System.out.println(-1);
        }
 
    }
 
    static void init() {
        index=0;
        finish = new boolean[V+1];
        parent = new int[V+1];
        discover = new int[V+1];
        list = new ArrayList[V+1];
        for(int i=1;i<=V;i++) list[i] = new ArrayList<>();
        st = new Stack<>();
        SCC = new ArrayList<>();
    }
    static int dfs(int cur){
        discover[cur] = ++index;
        st.push(cur);
 
        int parent = discover[cur];
        for (Integer next : list[cur]) {
            if (discover[next]==0) parent = Math.min(dfs(next),parent);
            else if(!finish[next]) parent = Math.min(parent,discover[next]);
        }
 
        if(parent==discover[cur]){
            ArrayList<Integer> scc = new ArrayList<>();
            while(true){
                Integer pop = st.pop();
                scc.add(pop);
                finish[pop] = true;
                if(pop==cur) break;
            }
            SCC.add(scc);
        }
        return parent;
    }
}