[백준]단절점(11266)

• 무향 연결 그래프에서 하나의 정점과 연결된 간선들을 제거했을 때 두개의 연결 그래프로 나뉘어 진다면 해당 정점은 단절점이다.
  
• 그래프에서 2번에 연결된 간선을 제거하면 다음과 같은 모양이 나온다 하지만 이는 단절점이 아니다.
  
• 4번에 연결된 간선을 제거하면 다음과 같은 모양이고 이는 단절점이다.
  
• 단절점을 구하는 공식 ( order : 정점의 방문순서, low : 자신을 거치지 않고 방문 가능한 정점들의 order 중 가장 작은 값, child : 정점의 자식 트리 수 )
  • A가 시작정점이 아닌 경우
    • orderA <= lowB -> A는 단절점
    • orderA > lowB -> A는 단절점이 아님
  • A가 시작정점인 경우
    • 2 <= childA -> A는 단절점
    • 2 > childA -> A는 단절점이 아님

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int count = 1;            // 방문 순서

    static int[] dis;                
    static boolean[] isCutVertax;    // 단절점

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.valueOf(st.nextToken()) + 1;    // 정점의 개수
        int M = Integer.valueOf(st.nextToken());        // 간선의 개수

        ArrayList<Integer> list[] = new ArrayList[N];

        dis = new int[N];
        isCutVertax = new boolean[N];

        for (int i = 0; i < N; i++) {
            list[i] = new ArrayList<>();
        }

        // 인접리스트
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list[a].add(b);
            list[b].add(a);
        }

        for (int i = 1; i < N; i++) {
            if (dis[i] == 0) {
                dfs(i, true, list);
            }
        }
        int cnt = 0;
        for (int i = 1; i < N; i++) {
            if (isCutVertax[i]) {
                cnt++;
            }
        }
        System.out.println(cnt);
        for (int i = 1; i < N; i++) {
            if (isCutVertax[i]) {
                System.out.print(i + " ");
            }
        }

    }

    private static int dfs(int vertax, boolean root, ArrayList<Integer>[] list) {
        dis[vertax] = count++;    // 방문 순서 저장
        int ret = dis[vertax];
        int child = 0;

        for (int no : list[vertax]) {
            if (dis[no] == 0) {
                child++;

                int low = dfs(no, false, list);

                if (!root && low >= dis[vertax]) {    // 시작정점이 아닌 경우
                    isCutVertax[vertax] = true;
                } 
                ret = Math.min(ret, low);
            } else {
                ret = Math.min(ret, dis[no]);
            }
        }

        if (root && child >= 2) {    // 시작정점인 경우
            isCutVertax[vertax] = true;
        } 

        return ret;
    }
}