백준 16583번: Boomerangs [C++]

작성일 | In
플래티넘 I 플래티넘 I

문제

Boomerangs

풀이

만약 그래프가 트리의 형태로 주어진다고 생각해 봅시다.

어떤 정점의 자식의 개수가 짝수인 경우, 두개씩 묶어 부메랑을 만듭니다.

홀수인 경우, 두개씩 묶고 남은 하나와 자신의 부모를 묶어 부메랑을 만듭니다. 이때 부모와 연결된 간선을 끊어 부모가 현재 노드를 자식으로 세지 않도록 합니다.

해당 방법을 이용해 부메랑을 만들면 부모가 존재하지 않는 루트 노드의 경우를 제외하고 모든 간선을 부메랑에 포함시킬 수 있습니다. 부모 노드의 경우 자식이 홀수인 경우 간선 하나를 부메랑으로 사용할 수 없으므로 총 간선의 개수를 $M$개라 할 때 $\lfloor M \rfloor$개의 부메랑을 만들 수 있습니다.

주어지는 그래프를 트리의 형태로 생각하고 풀어 봅시다.

임의의 루트 노드를 하나 잡고 깊이 우선 탐색을 이용해 깊이가 제일 깊은 노드부터 연결된 노드들을 자식 노드라 생각하고 부메랑을 만들어 줍니다.

이때 같은 간선을 여러번 사용하면 안 되므로

  1. 연결된 노드가 현재 노드를 탐색한 이후 바로 다음에 탐색되었고 자식 노드의 개수가 홀수인 경우 해당 노드와 연결된 간선은 고려하지 않습니다.
  2. 깊이가 깊은 노드에서 깊이가 얕은 노드로 가는 간선은 고려하지 않습니다.

이러한 방법 대신 각 간선마다 번호를 주고 사용여부를 체크하는 방법도 있습니다.

주어지는 그래프가 연결 그래프가 아닐 수 있음에 유의합시다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define ASSERT(x) assert(x)
#else
#define ASSERT(ignore) ((void)0)
#endif
using namespace std;

vector<tuple<int, int, int>> boomerangs;

vector<int> adj[101010];
int level[101010], parent[101010], childCnt[101010];

void dfs(int node, bool isRoot, vector<bool>& visited) {
    visited[node] = true;

    int prev = -1;
    for (int child : adj[node]) {
        if (child == parent[node])
            continue;

        if (not visited[child]) {
            level[child] = level[node] + 1;
            parent[child] = node;
            dfs(child, false, visited);
        } else if (level[child] < level[node])
            continue;

        if (childCnt[child] & 1 and parent[child] == node)
            continue;

        childCnt[node]++;

        if (prev == -1) {
            prev = child;
            continue;
        }
        boomerangs.emplace_back(prev, node, child);
        prev = -1;
    }

    if (not isRoot and prev != -1)
        boomerangs.emplace_back(prev, node, parent[node]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    boomerangs.reserve(M >> 1);
    vector<bool> visited(N + 1);
    for (int i = 1; i <= N; i++)
        if (not visited[i])
            dfs(i, true, visited);

    cout << boomerangs.size() << '\n';
    for (auto [i, j, k] : boomerangs)
        cout << i << ' ' << j << ' ' << k << '\n';

    return 0;
}

백준 16583번: Boomerangs [C++]