[백준] 그래프 트리 분할 22954번 (java)

출처 : https://www.acmicpc.net/problem/22954

 

풀이 방법

처음에는 유니온 파인드 문제인 줄 알았지만 굳이 구현할 필요는 없었다.

1. bfs 함수를 통해 트리를 만든다.

-> 1번에서 만든 트리의 노드가 n개 라면 -> 문제의 조건에서 1개 이상이기만 하면 되므로 마지막에 방문한 노드만 분리하고 답을 도출한다.

2. 만약 1번에서 구한 노드의 개수가 n보다 작으면 다음 방문을 안 한 노드를 기준으로 bfs를 진행한다.

-> 2번에서 진행한 bfs를 통해 구한 노드의 수의 합과 1번에서 구한 노드의 수의 합 n이 아니라면 2개 이상으로 분할이 되므로 -1을 출력

-> 만약 1, 2번에서 구한 노드의 수가 같으면 문제의 조건인 다른 개수의 노드를 가진 트리에 위반하므로 -1를 출력

 

주의 : 노드의 수가 1, 2개이면 두 개의 트리로 분리할 수 없다.

 

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

class Edge {
    int to, edgeNum;
    Edge(int to, int edgeNum) {
        this.to = to;
        this.edgeNum = edgeNum;
    }
}

public class P_22954 {
    static int n, m;
    static ArrayList<ArrayList<Edge>> graph = new ArrayList<>();
    static int[] visited = new int[100001];
    static List<Integer> ans1Node = new ArrayList<>(), ans1Edge = new ArrayList<>();
    static List<Integer> ans2Node = new ArrayList<>(), ans2Edge = new ArrayList<>();

    static int makeTree(int idx, List<Integer> nodes, List<Integer> edges) {
        int cnt = 1;
        Queue<Integer> q = new LinkedList<>();
        q.add(idx);
        visited[idx] = 1;
        nodes.add(idx);
        while (!q.isEmpty()) {
            int cur = q.poll();
            for (Edge edge : graph.get(cur)) {
                int next = edge.to;
                if (visited[next] == 0) {
                    visited[next] = 1;
                    q.add(next);
                    cnt++;
                    nodes.add(next);
                    edges.add(edge.edgeNum);
                }
            }
        }
        return cnt;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        

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

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int edgeNum = i + 1;
            graph.get(a).add(new Edge(b, edgeNum));
            graph.get(b).add(new Edge(a, edgeNum));
        }
        
        if (n == 1 || n == 2) {
            System.out.println(-1);
            return;
        }
        int ret1 = 0, ret2 = 0;
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (visited[i] == 0) {
                if (cnt == 0) {
                    ret1 = makeTree(i, ans1Node, ans1Edge);
                    if (ret1 == n) break;
                    cnt++;
                } else if (cnt == 1) {
                    ret2 = makeTree(i, ans2Node, ans2Edge);
                    break;
                }
            }
        }

        if (ret1 + ret2 != n || ret1 == ret2) {
            System.out.println(-1);
            return;
        }    

        if (ret1 == n) { // 모두 연결된 트리 -> 마지막 노드만 제거
        	System.out.println((ans1Node.size()-1) + " " + 1);
        	printList(ans1Node, ans1Node.size() - 1);
        	printList(ans1Edge, ans1Edge.size() - 1);
        	System.out.println((ans1Node.get(ans1Node.size()-1))); 
        }
        else { // 두 개로 분리된 트리
        	System.out.println(ans1Node.size() + " " + ans2Node.size());
            printList(ans1Node, ans1Node.size());
            printList(ans1Edge, ans1Edge.size());
            printList(ans2Node, ans2Node.size());
            printList(ans2Edge, ans2Edge.size());	
        }
        
    }

    static void printList(List<Integer> list, int size) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0;i < size;i++) {
        	sb.append(list.get(i)).append(' ');
        }                
        System.out.println(sb);
    }
}