[백준] 11400번 단절선 (JAVA)

문제

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

11400번: 단절선

 

설명

그 간선을 제거했을 때 그래프가 두 개 또는 그 이상으로 나누어지는 간선을 단절선이라 말한다.
즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 간선을 말한다.

먼저 간선 정보를 저장할 CutLine 클래스를 만들고 단절선을 저장할 배열인 cutList를 만든다.

나중에 단절선을 사전순으로 출력해야 하므로 Comparable 인터페이스를 이용한다.

class CutLine implements Comparable<CutLine>{
    int startNode;
    int endNode;

    public CutLine(int startNode, int endNode) {
        this.startNode = startNode;
        this.endNode = endNode;
    }

    @Override
    public int compareTo(CutLine c1) {
        int comp = this.startNode - c1.startNode;

        if (comp == 0) {
            return this.endNode - c1.endNode;
        }
        else
            return comp;
    }
}

백준 11266번 문제처럼 방문하지 않은 정점을 시작으로 DFS 탐색을 수행한다.

각 정점의 방문 순서와 minOrder를 비교하여 단절선을 찾아내야 한다.

해당 정점과 인접한 정점들을 하나씩 탐색하는데 방문한 정점을 만났고 현재 간선이 이전 정점으로 가는 간선이 아니라면 minOrder를 조건에 맞춰 최신화시켜준다.

자신의 방문 순서보다 minOrder가 작다면 curNode와 parNode를 잇는 간선은 단절선이 된다.

단절선에 해당하는 간선들은 모두 cutList에 추가하고 오름차순으로 정렬하여 출력한다.

int cutEdgeSearch(int curNode, int parNode) {
    // 자신의 방문 순서를 기록
    visited[curNode] = visitOrder++;

    // 방문한 점의 인접한 minOrder
    int minOrder = visited[curNode];

    for (int i = 0; i < adjList.get(curNode).size(); i++) {
        int destNode = adjList.get(curNode).get(i);

        // 만일 방문을 한 곳이라면
        if (visited[destNode] != 0) {
            // 해당 간선이 이전(부모)으로 가는 간선이 아니라면
            if (destNode != parNode) {
                minOrder = Math.min(minOrder, visited[destNode]);
            }
            continue;
        }

        // DFS를 진행하여 자식 노드들의 minOrder(low)를 가져온다
        int childOrder = cutEdgeSearch(destNode, curNode);

        // 자신의 순서(order) < low 라고 한다면 이는 단절선
        if (childOrder > visited[curNode]) {
            int a = curNode;
            int b = destNode;

            if (a > b) {
                int temp = a;
                a = b;
                b = temp;
            }

            cutList.add(new CutLine(a, b));
        }

        minOrder = Math.min(minOrder, childOrder);
    }

    return minOrder;
}

 

전체 코드

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

    static int V, E;
    static ArrayList<ArrayList<Integer>> adjList;
    static ArrayList<CutLine> cutList;
    static int[] visited;
    static boolean[] isCutEdge;
    static int cutEdgeCnt, visitOrder;

    static class CutLine implements Comparable<CutLine>{
        int startNode;
        int endNode;

        public CutLine(int startNode, int endNode) {
            this.startNode = startNode;
            this.endNode = endNode;
        }

        @Override
        public int compareTo(CutLine c1) {
            int comp = this.startNode - c1.startNode;

            if (comp == 0) {
                return this.endNode - c1.endNode;
            }
            else
                return comp;
        }
    }

    static int cutEdgeSearch(int curNode, int parNode) {
        // 자신의 방문 순서를 기록
        visited[curNode] = visitOrder++;

        // 방문한 점의 인접한 minOrder
        int minOrder = visited[curNode];

        for (int i = 0; i < adjList.get(curNode).size(); i++) {
            int destNode = adjList.get(curNode).get(i);

            // 만일 방문을 한 곳이라면
            if (visited[destNode] != 0) {
                // 해당 간선이 이전(부모)으로 가는 간선이 아니라면
                if (destNode != parNode) {
                    minOrder = Math.min(minOrder, visited[destNode]);
                }
                continue;
            }

            // DFS를 진행하여 자식 노드들의 minOrder(low)를 가져온다
            int childOrder = cutEdgeSearch(destNode, curNode);

            // 자신의 순서(order) < low 라고 한다면 이는 단절선
            if (childOrder > visited[curNode]) {
                int a = curNode;
                int b = destNode;

                if (a > b) {
                    int temp = a;
                    a = b;
                    b = temp;
                }

                cutList.add(new CutLine(a, b));
            }

            minOrder = Math.min(minOrder, childOrder);
        }

        return minOrder;
    }

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        adjList = new ArrayList<>();
        for (int i = 0; i <= V; i++) {
            adjList.add(new ArrayList<>());
        }

        cutList = new ArrayList<>();

        // 방문 순서 체크
        visited = new int[V + 1];

        // 단절선 여부
        isCutEdge = new boolean[V + 1];

        cutEdgeCnt = 0;
        visitOrder = 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());

            adjList.get(A).add(B);
            adjList.get(B).add(A);
        }

        for (int i = 1; i <= V; i++) {
            if (visited[i] == 0)
                cutEdgeSearch(i, 0);
        }

        Collections.sort(cutList);

        System.out.println(cutList.size());
        for (CutLine cutLine : cutList) {
            System.out.println(cutLine.startNode + " " + cutLine.endNode);
        }
    }
}