[DFS] 단절점

백준 11266 단절점

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

자신의 자손(다음) Vertex가 자신을 거치지 않고 자신의 조상(이미 거쳐왔던 곳)에 도달할 수 없으면 단절점이다.

인접리스트로 바꾸면 좀 더 빨라질 것 같음.

package com.company;

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

public class Main {

    static int V, E;
    static int[] order; //방문여부
    static int[] cutVertex; //단절점

    static int[][] map;
    static final int INF = 20000;
    static int seq=1;


    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        order = new int[V+1];
        cutVertex = new int[V+1];
        map = new int[V+1][V+1];

        for(int i=0; i<E; i++) {
            st = new StringTokenizer(br.readLine());
            int a=Integer.parseInt(st.nextToken());
            int b=Integer.parseInt(st.nextToken());

            map[a][b] = 1;
            map[b][a] = 1;
        }


        for(int i=1; i<=V; i++) {
            if(order[i]==0) {
                dfs(i, true);
            }
        }

        //출력
        int cutVertexCount=0;
        for(int i=0; i<cutVertex.length; i++){
            if(cutVertex[i]==1) cutVertexCount++;
        }

        System.out.println(cutVertexCount);
        for(int i=1; i<=V; i++) {
            if(cutVertex[i]==1) System.out.printf("%d ", i);
        }

    }

    //low를 Retrun
    public static int dfs(int vertex, boolean isRoot) {

        int rootCount=0;
        order[vertex] = seq++;
        int retu = order[vertex];

        //자식검사
        for(int i=1; i<=V; i++){

            if(map[vertex][i]==1){
                if(order[i]==0){ //갈 수 있는 곳

                    rootCount++;
                    int low = dfs(i, false);

                    //자식이 나를 우회할 수 없음
                    if(order[vertex] <= low && !isRoot){
                        cutVertex[vertex]=1;
                    }

                    retu = Math.min(retu, low);
                }else{ //이미 간 곳
                    retu = Math.min(retu, order[i]); //이부분 간지 (이미 간곳은 건드리기?만 한다)
                }

            }
        }//for - 자식검사

        //루트 검사
        if(isRoot && 1<rootCount){
            cutVertex[vertex]++;
        }

        return retu;
    }


}

예제 테스트케이스. (8은 없는 것)

[틀렸던 부분1]

단절점은 중복해서 체크될 수 있다. 예를들면 7번노드는 3번노드, 2번노드 모두에 의해 단절점으로 판명된다. 

때문에 단절점 기록을 List에 add하게 되면 중복된 값이 들어가게 된다. 

static int[] cutVertex; //단절점

그래서 중복되지 않게 행렬에 기록해야 한다.

[틀렸던 부분2]

첫째항에 seq가 0이 들어가면 안된다. order[첫번째노드]==0에 체크되어서 방문하지 않았던 노드로 간주된다.

2번째 풀이

package 단절점;

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

public class Main {

    static int V; //정점의 수 ~10,000
    static int E; //간선의 수 ~100,000
    static List<Integer>[] map;
    static int[] cutVertex; //단절점


    static int[] order; //각 정점의 방문순서
    static int seq; //전체 방문순서 카운터


    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        order = new int[V+1]; //0이면 방문을 하지 않은 상태
        cutVertex = new int[V+1];

        seq = 1;

        //몇개 안되니까 초기화를 다 시킨다
        map = new ArrayList[V+1];
        for(int i=1; i<=V; i++){
            map[i] = new ArrayList<>();
        }

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

        //forest가 2개 이상일 수 있으므로.
        for(int i=1; i<=V; i++){
            if(order[i]==0) dfs(i, true);
        }

        //출력
        int cutPointCount = 0;
        for(int i=1; i<=V; i++){
            if(cutVertex[i]==1) cutPointCount++;
        }

        System.out.println(cutPointCount);

        for(int i=1; i<=V; i++){
            if(cutVertex[i]==1) System.out.printf("%d ", i);
        }
    }


    /**
     * 어떤(now)의 다음 노드(next)가  now노드를 거치지 않고 그 앞의 애들에게 접근할 수 없으면 단절점.
     * 리턴값은 탐색가능한 노드 중 seq가 가장 작은 노드의 seq.
     *
     * [예외] root의 경우는 자손이 2개 이상이면 단절점.
     */
    static int dfs(int now, boolean isRoot){

        order[now] = seq++; //현재노드의 방문번호
        int retu = order[now]; //가장 말단이면 자기 자신의 order를 반환
        int childCount=0;


        //다음노드 검사
        for(int next: map[now]){

            if(order[next]==0){ //새로운 곳(탐색O)

                childCount++;
                int dfs = dfs(next, false);
                if( order[now]<=dfs && !isRoot ){
                    System.out.printf("단절점추가:%d(%d) %d(%d)\n", now, order[now], next, dfs);
                    cutVertex[now]=1; //다음노드가 나 이전으로 가지 못하면 나는 단절점
                }
                retu = Math.min(retu, dfs);

            }else { //이미 갔던 곳: order만 가져온다 (탐색X)
                retu = Math.min(retu, order[next]);
            }
        }

        //루트이면서 연결지점이 2개이상인 경우 단절점
        if( isRoot && 2<=childCount ) cutVertex[now]=1;

        return retu;
    }
}

두번째로 풀었는데 첫번째만큼 시간이 오래걸렸다. 멀쩡히 위에거를 보면서도 잘못된 점을 못찾아서 시간이 한참 걸렸다.

처음에 풀었을때는 인접행렬인데 이것은 인럽리스트로 풀었다. 덕분에 시간은 절반으로 감소했다.

[틀렸던부분]

인접리스트니까 루트를 체크할때 하위노드의 갯수가 2이상이면 자식이 2개이상이니까 단절점으로 간주했다.

연결된 노드가 2개가 아니라 실제로 거기로 이동한 것만 세야한다.

반례는 노드3개가 cycle로 연결된 걸 생각해보면 된다.

if( isRoot && 2<=map[now].size() ) cutVertex[now]=1;

잘못된 작성했었던 부분

참고사이트

http://jason9319.tistory.com/119

http://willbfine.tistory.com/252

http://bowbowbow.tistory.com/3