백준 11400번 단절선 java 풀이

문제

그래프가 주어졌을 때, 단절선을 모두 구해 출력하는 프로그램을 작성하시오.

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

입력

첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이며, 방향은 양방향이다.

그래프는 항상 연결되어 있으며, 같은 간선이 두 번 이상 들어오는 경우는 없다. 또, A와 B가 같은 경우도 없다.

그래프의 정점은 1부터 V까지 자연수이다.

출력

첫째 줄에 단절선의 개수 K를 출력한다.

둘째 줄부터 K개 줄에는 단절선을 사전순으로 한 줄에 하나씩 출력한다. 간선은 "A B" 형식으로 출력해야 하고, A < B를 만족해야 한다. 같은 간선은 한 번만 출력하면 된다. 즉, "A B"를 출력한 경우에 "B A"는 출력할 필요가 없다.

예제 입력 1 복사

7 8
1 4
4 5
5 1
1 6
6 7
2 7
7 3
2 3

예제 출력 1 복사

2
1 6
6 7

 

 

단절점 문제와 유사한 문제이다.

다른점은 단절점을 찾는 것이 아니라 단절선을 찾아야 했다.

 

문제의 로직

단절점 문제와 거의 유사하나 단절선을 찾기 위해서 최소 방문순서가 현재 방문순서보다 더 크거나 같으면 선을 찾아주는 것이 아니라 최소 방문순서가 현재 방문순서보다 더 크다면 해당 선을 new Node(x,y)를 통해서 저장해 주었다. 같을때도 조건을 추가하면 간선을 찾는것이 아니라 정점이 찾아지기 때문

 

- java 코드

import java.io.*;
import java.util.*;


public class Main {
    static int count = 1; // 방문 순서
    static int[] order;
    static boolean[] isCutVertax; // 단절점

    static List<Node> ans;

    public static class Node {
         int x;
         int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

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

        int V = Integer.valueOf(st.nextToken()); // 정점의 개수
        int E = Integer.valueOf(st.nextToken()); // 간선의 개수

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

        // 양방향 인접 리스트 구현.
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());

            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

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

//        for(int i = 1 ; i <= E; i++){
//            System.out.print(a.get(i) + " ");
//            System.out.println();
//        }

        order = new int[V + 1];
        ans = new ArrayList<>();

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

        Collections.sort(ans, (a1, a2) -> (a1.x == a2.x) ? a1.y - a2.y : a1.x - a2.x);

        StringBuilder sb = new StringBuilder();
        sb.append(ans.size() + "\n");

        for (int i = 0; i < ans.size(); i++) {
            sb.append(ans.get(i).x + " " + ans.get(i).y+"\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    public static int dfs(int vertax, int parent, ArrayList<ArrayList<Integer>> a) {
        order[vertax] = count++; // 방문 순서 저장
        int ret = order[vertax];

        // 자식 검사
        for (int now : a.get(vertax)) {
            if (now == parent) {
                continue;
            }
            if (order[now] == 0) {

  
                int low = dfs(now, vertax, a);

         
                if (low >= order[vertax]) {
                    if (now > vertax) {
                        ans.add(new Node(vertax, now));
                    } else {
                        ans.add(new Node(now, vertax));
                    }
                }
                ret = Math.min(ret, low);
            } else { 
                ret = Math.min(ret, order[now]);
            }
        }
        
        return ret;
    }
}