[BOJ] 백준 [11266] 단절점 JAVA

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

11266번: 단절점

문제

풀이

단절점이란 쉽게말해 아무 정점 X 가 있고 X의 자식들끼리 서로 이동할 때 , 꼭 X를 지나야만
왕래가 가능하면 단절점이라고 부른다.
즉 , X를 지나지 않고 다른 우회경로를 통해서 지날 수 있다면 X는 단절점이 아니게 된다.

그럼 우회경로가 있는지 어떻게 알아낼수 있을까
아무 정점 하나 잡아서 DFS를 돌리면서 정점이 처음 방문될때 마다 방문순서를 매겨주자.
DFS특성상 처음부터 시작해서 끝까지 재귀로 우선 탐색을 한다.

그리고 탐색할때 마다 탐색된 노드A의 인접노드 중 , A의 방문순서보다 작은 값을 반환해준다. 
ret = Math.min(ret,discover[next]);

그렇게 DFS의 결과값(int prev = dfs(next))으로서 반환된 값이 A의 방문순서보다 작다 ?
if(prev < discover[cur])
그러면 A 입장에서는 왜 나를 거치지도 않았는데 내 자식노드들이 내 순서보다 작은값을 가지고있지 ..?
=> 우회 경로가 있다. => 단절점 X

A의 방문순서보다 높다 ? 
A입장에서는 역시 나를 거쳐야만 지나갈 수 있네 ..?
=> 우회 경로없음. => 단절점 O

이런식으로 해결하면 노드를 하나하나 없애고 DFS를 돌리는 O(N^2)의 시간복잡도 보다 더 빨리 해결이 가능하다.

그런데 , 예외가 있다. 바로 시작노드가 root이면서 자식이 둘 이상일때.
if(isRoot && child>=2)
트리를 떠올려보면 root가 없으면 바로 다른 서브트리가 최소 둘이상으로 나눠지기 때문에 단절점임.

 

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
 
public class Main {
    static int V,E,order=1,cnt=0;
    static int[] discover;
    static ArrayList<Integer>[] list;
    static boolean[] isCutVertex;
 
    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];isCutVertex = new boolean[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,true);
 
        StringBuilder sb = new StringBuilder();
        for(int i=1;i<=V;i++) {
            if(isCutVertex[i]){
                cnt++;
                sb.append(i).append(" ");
            }
        }
        System.out.println(cnt);
        System.out.println(sb);
 
    }
 
    private static int dfs(int cur,boolean isRoot) {
        discover[cur] = order++;
        int ret = discover[cur];
        int child=0;
 
        for (int next : list[cur]) {
            if(discover[next]==0) {
                child++;
 
                int prev = dfs(next,false);
 
                if(!isRoot && prev >= discover[cur])
                    isCutVertex[cur]=true;
                ret = Math.min(ret,prev);
            }else
                ret = Math.min(ret,discover[next]);
        }
 
        if(isRoot && child>=2)
            isCutVertex[cur]=true;
        return ret;
    }
 
}