BOJ 백준 22954번 그래프 트리 분할

 

BOJ 백준 22954 그래프 트리 분할

문제: https://www.acmicpc.net/problem/22954

22954번: 그래프 트리 분할

 

정점 N개, 간선 M개의 그래프가 주어졌을 때 서로 다른 크기의 2개의 트리로 분할하라는 문제이다.

 

문제에서 주어지는 그래프에는 특별한 제약 사항이 없으므로 이미 그래프가 여러 개의 연결 요소로 분할되어 있을 수도 있다. 그래서 그래프의 연결 요소 개수를 찾아야 하는데, 이는 DFS(Depth First Search)로 간단히 구할 수 있다. 연결 요소를 구하는 문제는 아래를 참조하면 된다.

 

 

 

▶ 그래프의 연결 요소 개수 구하는 문제 (BOJ 11724)

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

11724번: 연결 요소의 개수

 

 

 

이미 그래프가 3개 이상의 연결 요소로 분할되어 있는 경우에는 두 개의 트리로 분할이 불가능하다. 또한 이미 2개의 연결 요소로 분할되어 있는 경우에는 각 연결 요소에 속한 트리의 크기가 서로 같을 때 그래프 분할이 불가능하다. 그러면 각 연결 요소에 속한 트리를 구해야 하는데, 이도 마찬가지로 DFS로 해결 가능하다. DFS로 방문하는 경로 상에 있는 정점과 간선으로 트리를 구성할 수 있다.

 

 

 

하나의 연결 요소로만 그래프가 주어지는 경우가 관건인데, 이 때는 반드시 그래프 분할이 필요하다. 그런데 어차피 분할할 수 있는 모든 케이스 중에서 아무거나 한 가지를 찾으면 된다. 정점 한 개짜리도 엄연히 트리이므로 앞에서 말한 바처럼 DFS로 연결 요소에 속한 트리를 하나 구하고, 찾은 트리에서 임의의 한 개의 leaf node만 분리해 주면 된다.

 

Leaf node를 구하는 방법은 크게 어렵지 않은데, DFS 과정에서 방문 중인 정점에서 더 이상 나아갈 수 있는 간선이 없을 때 해당 정점이 leaf node가 된다. 구한 leaf node 중 한 개만 이미 방문 처리를 해줘서 해당 정점을 제외하고 다시 DFS로 트리를 구하면 leaf 노드로 구성된 트리 하나와 나머지 정점으로 구성된 트리 하나가 나올 것이다.

 

마지막으로 두 개의 트리의 크기가 같은지 판단하고, 크기가 같으면 분할이 불가능하므로 -1을 출력해준다.

 

 

 

아이디어 자체는 크게 어렵지 않은데, 각 트리의 크기와 속한 정점, 그리고 속한 간선을 각각 출력해야 하는 점이 조금 까다로웠다. 트리를 구성하는 정점을 저장하는 배열과 간선을 저장하는 배열을 각각 선언해서 사용하면 해결 가능하다.

 

 

 

#include <cstdio>
#include <tuple>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
using pp = pair<int, int>;

const int N_MAX = (int)1e5;

int n, m, treeNum;
bool visited[N_MAX + 1];
bool isLeaf[N_MAX + 1];

vector<pp> edges[N_MAX + 1];
vector<int> treeNodes[N_MAX + 1];
vector<int> treeEdges[N_MAX + 1];

void go(int now, int idx){
    visited[now] = true;
    treeNodes[idx].push_back(now);
    bool leaf = true;
    for (pp e: edges[now]){
        int next = e.first;
        int edgeNum = e.second;
        if (!visited[next]){
            treeEdges[idx].push_back(edgeNum);
            leaf = false;
            go(next, idx);
        }
    }
    isLeaf[now] = leaf;
    
    return;
}

void print(vector<int> v){
    sort(v.begin(), v.end());
    for (int x: v){
        printf("%d ", x);
    }
    printf("\n");
}

int main(){
    scanf("%d %d", &n, &m);
    
    for (int i = 1; i <= m; i++){
        int u, v; scanf("%d %d", &u, &v);
        edges[u].push_back({v, i});
        edges[v].push_back({u, i});
    }
    
    for (int i = 1; i <= n; i++){
        if (!visited[i]){
            go(i, treeNum);
            treeNum += 1;
        }
    }
    
    // 이미 그래프가 세 개 이상의 부분으로 분리되어 있으면
    if (treeNum > 2){
        printf("-1\n");
        return 0;
    }
    
    int startV = 0, selected = 0;
    
    // 그래프를 두 개의 트리로 분래해야 하면
    if (treeNum < 2){
        // 리프 노드 하나 골라서 분리
        for (int x: treeNodes[0]){
            if (isLeaf[x]){
                selected = x;
            }
            else {
                startV = x;
            }
        }
        
        treeNodes[0].clear();
        treeEdges[0].clear();
        memset(visited, false, sizeof(visited));
        visited[selected] = true;
        go(startV, 0);
        
        treeNodes[1].push_back(selected);
    }
    
    
    // 두 부분의 크기가 서로 같을 때
    if ((int)treeNodes[0].size() == (int)treeNodes[1].size()){
        printf("-1\n");
        return 0;
    }
    printf("%d %d\n", (int)treeNodes[0].size(), (int)treeNodes[1].size());
    
    print(treeNodes[0]);
    print(treeEdges[0]);
    
    print(treeNodes[1]);
    print(treeEdges[1]);
    
    return 0;
}