boj-11266 단절점

• 절단점(cut vertex): 어떤 무향 그래프의 절단점이란 이 점과 인접한 간선들을 모두 지웠을 때 해당 컴포넌트가 2개 이상으로 나뉘어지는 정점을 말한다.

• 위 그래프에서 1, 3, 5 정점이 각각 절단점이다.

각 지점 별로 탐색하면서, 자식의  depth가 자신의 depth보다 크거나 같다면 단절점이다.

root의 경우 child node가 2이상이면 단절점이다.

DFS 

static int dfs(int here, int d, boolean root) {
        D[here] = d;
        int ret = D[here];
        int child = 0;
        for (int there: VT[here]) {
            if(D[there]==0) {
                child++;
                int df = dfs(there, d+1, false);
                if(!root && df>= D[here]) C[here] = true;
                ret = Math.min(ret, df);
            } else {
                ret = Math.min(ret, D[there]);
            }
        }
        if(root&&child>1) C[here] = true;

        return ret;
    }

 

전체 코드

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

public class boj11266 {
    static int V, E;
    static int[] D;
    static boolean[] C;
    static ArrayList<Integer>[] VT;
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/input_boj11266.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        VT = new ArrayList[V+1];
        D = new int[V+1];
        C = new boolean[V+1];
        for (int i = 1; i <= V ; i++) VT[i] = new ArrayList<>();

        int a, b;
        for (int i = 1; i <= E ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            VT[a].add(b);
            VT[b].add(a);
        }

        for (int i = 1; i <= V ; i++) {
            dfs(i, 1, true);
        }

        int result = 0;
        for (int i = 1; i <= V ; i++) {
            if(C[i]) result++;
        }
        System.out.println(result);
        for (int i = 1; i <= V ; i++) {
            if(C[i]) System.out.print(i+ " ");
        }
    }

    static int dfs(int here, int d, boolean root) {
        D[here] = d;
        int ret = D[here];
        int child = 0;
        for (int there: VT[here]) {
            if(D[there]==0) {
                child++;
                int df = dfs(there, d+1, false);
                if(!root && df>= D[here]) C[here] = true;
                ret = Math.min(ret, df);
            } else {
                ret = Math.min(ret, D[there]);
            }
        }
        if(root&&child>1) C[here] = true;

        return ret;
    }
}