[BOJ] 백준 [11400] 단절선 JAVA

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

11400번: 단절선

문제

https://katastrophe.tistory.com/70 이전 포스팅 참고 ( 단절점 )

풀이

단절점 찾기랑 원리가 같다.
다른점은 DFS를 진행할때 부모노드를 기록해 나가는 것.

만약 정점 A의 자식노드보다 더 낮은 값이 DFS결과로서 리턴이 되면 우회로가 존재
그렇지 않다면 해당 노드는 단절점이므로 , 이 단절점의 부모노드와의 Edge를 list에 넣고 정렬하면 끝

 

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
 
public class Main {
    static int V,E,order=1;
    static int[] discover;
    static ArrayList<Integer>[] list;
    static ArrayList<int[]> cutEdge = new ArrayList<>();
 
    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];
        list = new ArrayList[V+1];
        discover = new int[V+1];
 
        for(int i=1;i<=V;i++) list[i] = new ArrayList<>();
 
        for(int i=1;i<=E;i++) {
            input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            list[input[0]].add(input[1]); list[input[1]].add(input[0]);
        }
 
        for(int i=1;i<=V;i++)
            if(discover[i]==0) dfs(i,0);
        cutEdge.sort((o1, o2) -> o1[0]!=o2[0] ? o1[0]-o2[0] : o1[1]-o2[1]);
 
        System.out.println(cutEdge.size());
        for (int[] edge : cutEdge)
            System.out.println(edge[0]+" "+edge[1]);
    }
 
    private static int dfs(int cur,int parent) {
        discover[cur] = order++;
        int ret = discover[cur];
 
        for (int next : list[cur]) {
            if(next==parent) continue;
            if(discover[next]==0) {
                int prev = dfs(next,cur);
                if(prev > discover[cur])
                    cutEdge.add(new int[]{Math.min(cur,next), Math.max(cur,next)});
                ret = Math.min(ret,prev);
            }else ret = Math.min(ret,discover[next]);
        }
        return ret;
    }
}