22954. 그래프 트리 분할

문제

[BOJ-22954] 그래프 트리 분할

---

문제 해결 아이디어

BFS로 연결 컴포넌트와 스패닝 트리를 동시에 구성하고, 불가능 조건을 걸러낸 뒤 분할!

조건

• 그래프에서 간선 삭제만으로 서로 다른 크기의 트리 2개로 분할
• 각 트리는 연결 그래프여야 하고, 정점 및 간선 공유 불가
• N ≤ 100,000, M ≤ 200,000

불가능 조건

조건	이유
N ≤ 2	크기가 다른 두 트리로 나눌 수 없음 (1+1만 가능)
컴포넌트 수 ≥ 3	간선 삭제만으론 3개 이상의 조각을 2개로 합칠 수 없음
컴포넌트 수 = 2이고 크기가 같음	두 트리의 크기가 동일

BFS 스패닝 트리 접근

• BFS 탐색으로 각 연결 컴포넌트의 스패닝 트리 자동 구성
• parent[v], parentEdge[v] : BFS 트리에서 v의 부모 노드와 연결 간선 번호
• 루트 노드는 parent[root] = -1

분할 전략

케이스 1. 컴포넌트 1개 (연결 그래프)

• BFS 스패닝 트리에서 리프 노드 하나를 분리 → 크기 1 + (N-1)
• 리프 조건: parent[v] != -1 (루트 제외) && childCount[v] == 0

케이스 2. 컴포넌트 2개 (크기가 다름)

• 각 컴포넌트의 BFS 스패닝 트리를 그대로 출력

---

코드

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

public class BOJ_22954 {
    static int N, M;
    static List<List<int[]>> graph;
    static int[] parent;
    static int[] parentEdge;
    static boolean[] visited;

    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());

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

        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            graph.get(u).add(new int[]{w, i});
            graph.get(w).add(new int[]{u, i});
        }

        parent = new int[N + 1];
        parentEdge = new int[N + 1];
        visited = new boolean[N + 1];
        Arrays.fill(parent, -1);
        Arrays.fill(parentEdge, -1);

        List<List<Integer>> components = new ArrayList<>();
        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                List<Integer> comp = new ArrayList<>();
                bfs(i, comp);
                components.add(comp);
            }
        }

        int numComp = components.size();
        boolean impossible = N <= 2
                || numComp >= 3
                || (numComp == 2 && components.get(0).size() == components.get(1).size());

        if (impossible) {
            System.out.println(-1);
            return;
        }

        if (numComp == 1) {
            List<Integer> all = components.get(0);
            int[] childCount = new int[N + 1];
            for (int node : all) {
                if (parent[node] != -1) childCount[parent[node]]++;
            }

            int leaf = -1;
            for (int node : all) {
                if (parent[node] != -1 && childCount[node] == 0) {
                    leaf = node;
                    break;
                }
            }

            System.out.println("1 " + (N - 1));
            System.out.println(leaf);

            StringBuilder sbV = new StringBuilder();
            StringBuilder sbE = new StringBuilder();
            for (int node : all) {
                if (node == leaf) continue;
                if (sbV.length() > 0) sbV.append(' ');
                sbV.append(node);
                if (parent[node] != -1) {
                    if (sbE.length() > 0) sbE.append(' ');
                    sbE.append(parentEdge[node]);
                }
            }
            System.out.println(sbV);
            System.out.println(sbE);
        } else {
            List<Integer> c1 = components.get(0);
            List<Integer> c2 = components.get(1);

            System.out.println(c1.size() + " " + c2.size());
            printTree(c1);
            printTree(c2);
        }
    }

    static void printTree(List<Integer> comp) {
        StringBuilder sbV = new StringBuilder();
        StringBuilder sbE = new StringBuilder();
        for (int node : comp) {
            if (sbV.length() > 0) sbV.append(' ');
            sbV.append(node);
            if (parent[node] != -1) {
                if (sbE.length() > 0) sbE.append(' ');
                sbE.append(parentEdge[node]);
            }
        }
        System.out.println(sbV);
        System.out.println(sbE);
    }

    static void bfs(int start, List<Integer> comp) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        visited[start] = true;
        comp.add(start);

        while (!q.isEmpty()) {
            int u = q.poll();
            for (int[] e : graph.get(u)) {
                int next = e[0];
                int eid = e[1];
                if (!visited[next]) {
                    visited[next] = true;
                    parent[next] = u;
                    parentEdge[next] = eid;
                    q.offer(next);
                    comp.add(next);
                }
            }
        }
    }
}

---

예제 풀이

• N=5, M=5

그래프 구성:

간선 번호	연결
1	1 ↔ 2
2	1 ↔ 3
3	2 ↔ 3
4	3 ↔ 4
5	4 ↔ 5

---

BFS 스패닝 트리 (시작: 1):

노드	parent	parentEdge
1	-	-
2	1	1
3	1	2
4	3	4
5	4	5

---

리프 탐색:

노드	childCount	리프 여부
1	2	✗ (루트)
2	0	✓ ← leaf
3	1	✗
4	1	✗
5	0	✗ (2보다 늦게 발견)

---

출력 결과:

구분	출력
크기	1 4
트리1 정점	2
트리1 간선	(0개)
트리2 정점	1 3 4 5
트리2 간선	2 4 5

트리2 간선: parentEdge[3]=2 (1↔3), parentEdge[4]=4 (3↔4), parentEdge[5]=5 (4↔5)

sizes: 1 ≠ 4 → 정답