단절점 / 단절선

[WonYong-Jang]

단절점

하나의 컴포넌트로 이루어진 무방향 그래프에서 한 정점을 제거했을 때 그래프가 두개 이상의 컴포넌트(그래프)로 나누어지는 정점을 단절점

단절점 특징

• 어떤 정점 A에 연결된 모든 정점들 중 두 정점들 간에 정점 A를 거치지 않고 갈 수 있는 우회경로가 존재하지 않는 경우가 존재한다면 정점 A는 단절점으로 판단 가능 즉, 단절점에 바로 인접해 있는 정점들의 쌍은 단절점이 없으면 우회로로 인해 연결되어 있지 않다!

• 비효율적인 방법 : 모든 정점을 한번씩 선택(V) 하여 제거한 후 그래프가 나뉘어지는지 파악 ( V E) ==> 시간복잡도 O( V ( V + E))

• DFS 스패닝 트리를 이용하여 단절점을 빠른시간내에 구할수 있음

구현 방법

• dfs 를 이용하여 정점들의 방문 순서를 기록
• 특정 A번 정점에서 자식 노드들이 정점 A를 거치지 않고 정점 A보다 빠른 방문번호를 가진 정점으로 갈수 없다면 단절점이다.

예외 케이스

• 루트노드로 잡은 특정 노드의 자식 수가 2개 이상이면 무조건 단절점이다!

정점 A가 루트라면
==> 자식 수가 2개 이상이면 단절짐이다.
정점 A가 루트가 아니라면
==> A번 정점에서 자식 노드들이 정점 A를 거치지 않고 정점 A보다 빠른 방문번호를 가진 정점으로 갈 수 없다면 단절점

==>한번의 dfs 로 답을 구할수 있기 때문에 O(N + M) 

public class baek11266 {

    static int V, E, number;
    static boolean[] cut = new boolean[10005]; // 단절점 여부 확인 배열 ! 
    static int[] order = new int[10005]; // 방문 순서 기록 !! 
    static ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();
    public static void main(String[] args) throws IOException {
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        number =0; // 방문 순서 기록 할 숫자 

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

        int cnt =0;
        for(int i=1; i<= V; i++)
        {
            if(cut[i]) cnt++;
        }
        bw.write(cnt+"\n");
        for(int i=1; i<= V; i++)
        {
            if(cut[i]) 
            {
                bw.write(i+" ");
            }
        }
        bw.flush();
    }
    public static int dfs(int cur, int p)
    {
        order[cur] = ++number; // 방문순서 지정 
        int ret = order[cur];
        int child = 0; // root 자식 수가 2개 확인하기 위함 
        for(int next : adj.get(cur))
        {
                         if( next == p ) continue;
            if(order[next] > 0) // 이미 방문한 지점이라면 가장 작은 순서 찾아서 업데이트 
            {
                ret = min(ret, order[next]);
                continue;
            }

            child++;

            int prev = dfs(next, cur);

            if(p != 0 && prev >= order[cur]) {
                cut[cur] = true; // 단절점 
            }
            ret = min(ret, prev);
        }

        if(p ==0 && child >= 2) cut[cur] = true;

        return ret;
    }
}

단절선

public class Main {

    static int N, K, number;
    static int[] order = new int[100005];
    static ArrayList<Node> result = new ArrayList<>();
    static ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();
    public static void main(String[] args) throws IOException {

        for(int i=1; i<= N; i++)
        {
            if(order[i] > 0) continue;
            dfs(i, 0);
        }
    }
    public static int dfs(int cur, int p)
    {
        order[cur] = ++number;
        int ret = order[cur];

        for(int next : adj.get(cur))
        {
            if(next == p) continue;

            if(order[next] > 0)
            {
                ret = min(ret, order[next]);
                continue;
            }

            int prev = dfs(next, cur);

            if(prev > order[cur])
            {
                result.add(new Node(min(cur, next), max(cur, next)));
            }

            ret = min(prev, ret);
        }

        return ret;
    }
}

트리 에서의 단절점과 단절선 !! ( 사이클이 없는 ) / 주의!!

트리에서는 사이클이 존재하지 않기 때문에 단절선이 아닌 선은 없다!

단절점 같은 경우는 연결된 간선이 2개 이상이면 단절점 이다.

백준 14675 단절점과 단절선 문제

출처 : https://www.crocus.co.kr/1164