[Algorithm] cpp 백준 16583번: Boomerangs

문제

링크: BOJ 16583 — Boomerangs
요약: 무방향 단순 그래프에서 정점 v를 공유하는 두 간선 (u,v), (v,w)로 구성된 부메랑 <u, v, w>를 최대 개수로 만들기. 각 간선은 최대 한 번만 사용해야 함.

제한/스펙

1 ≤ N, M ≤ 100000
간선은 입력에 한 번만 등장하며, u < v
다중 컴포넌트 가능, 평행 간선 없음

입출력

1
2
입력: N M
다음 M줄: u v (간선)

1
2
출력: K (최대 부메랑 수)
다음 K줄: u v w (부메랑)

예시

접근 개요

핵심 아이디어: 각 정점 v에서 아직 사용되지 않은(미소모) incident 간선들을 둘씩 묶으면 <u, v, w> 부메랑을 만들 수 있음.
전역 일관성: DFS로 트리를 따라가며 각 정점에서 가능한 즉시 페어링. 미소모 간선이 홀수 개 남으면 그중 하나를 부모로 올라온 간선과 결합해 페어링하고, 그렇지 않으면 그 부모 간선을 상위로 “전파”.
보장: 한 정점당 미소모 간선이 최종적으로 0 또는 1개만 위로 전달되므로, 각 간선을 최대 한 번만 사용하면서도 가능한 모든 국소 페어링을 즉시 성사시켜 전역 최적(최대 개수)을 이룸.

알고리즘 설계

간선에 ID를 부여하고, 인접 리스트에 (이웃, 간선ID)를 저장.
visV[v], visE[id]로 정점/간선 방문 여부를 관리.
DFS(반복/스택 권장)로 내려가며, 이미 방문된 정점으로 향하는 간선을 v의 미소모 목록에 적재.
v 처리 종료 시:
- 미소모 목록에서 2개씩 꺼내 <u, v, w>를 만들어 답에 추가.
- 남은 1개가 있고 부모가 있으면, 그 1개와 parentEdge를 묶어 <u, v, parent>를 추가.
- 남은 것이 없고 부모가 있으면, parentEdge를 부모에게 미소모로 전달.
컴포넌트마다 시작 정점에서 위 과정을 반복.

올바름 근거(스케치)

각 간선은 최초로 처리되는 공통 정점에서만 사용되므로 중복 사용 불가 보장.
정점 기준의 즉시 페어링은 국소 최적이며, 미소모 1개만 상위로 전달하므로 전체적으로 최대 수량을 확보.
각 간선·정점은 O(1)회 처리되어 전체 복잡도는 O(N+M).

복잡도

시간: O(N+M)
공간: O(N+M)

구현 (C++)

 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
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

struct Edge { int a, b; };

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

    int N, M; 
    if(!(cin >> N >> M)) return 0;

    vector<Edge> edges(M);
    vector<vector<pair<int,int>>> adj(N+1);
    for(int i=0;i<M;++i){
        int u,v; cin >> u >> v;
        edges[i] = {u,v};
        adj[u].push_back({v,i});
        adj[v].push_back({u,i});
    }

    auto other = [&](int eid, int v){
        return edges[eid].a == v ? edges[eid].b : edges[eid].a;
    };

    vector<char> visV(N+1,0), visE(M,0);
    vector<vector<int>> unpaired(N+1);
    vector<array<int,3>> ans;

    struct Frame{int v,parent,parentEdge; size_t idx;};
    vector<Frame> st;

    for(int s=1;s<=N;++s){
        if(visV[s]) continue;
        st.push_back({s,-1,-1,0});
        while(!st.empty()){
            auto &f = st.back();
            if(!visV[f.v]) visV[f.v] = 1;
            if(f.idx < adj[f.v].size()){
                auto [u,eid] = adj[f.v][f.idx++];
                if(visE[eid]) continue;
                visE[eid] = 1;
                if(!visV[u]) st.push_back({u,f.v,eid,0});
                else unpaired[f.v].push_back(eid);
            }else{
                auto &vec = unpaired[f.v];
                while(vec.size() >= 2){
                    int e1 = vec.back(); vec.pop_back();
                    int e2 = vec.back(); vec.pop_back();
                    int u1 = other(e1, f.v);
                    int u2 = other(e2, f.v);
                    ans.push_back({u1, f.v, u2});
                }
                if(f.parent != -1){
                    if(!vec.empty()){
                        int e1 = vec.back(); vec.pop_back();
                        int u1 = other(e1, f.v);
                        ans.push_back({u1, f.v, f.parent});
                    }else{
                        unpaired[f.parent].push_back(f.parentEdge);
                    }
                }
                st.pop_back();
            }
        }
    }

    cout << (int)ans.size() << '\n';
    for(auto &t: ans) cout << t[0] << ' ' << t[1] << ' ' << t[2] << '\n';
    return 0;
}

구현 (Python)

 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
# 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
import sys
sys.setrecursionlimit(1_000_000)
input = sys.stdin.readline

def solve():
    N, M = map(int, input().split())
    edges = [None]*M
    adj = [[] for _ in range(N+1)]
    for i in range(M):
        u, v = map(int, input().split())
        edges[i] = (u, v)
        adj[u].append((v, i))
        adj[v].append((u, i))

    def other(eid, v):
        a, b = edges[eid]
        return b if a == v else a

    visV = [False]*(N+1)
    visE = [False]*M
    unpaired = [[] for _ in range(N+1)]
    ans = []

    stack = []
    for s in range(1, N+1):
        if visV[s]:
            continue
        stack.append([s, -1, -1, 0])  # v, parent, parentEdge, idx
        while stack:
            v, parent, parentEdge, idx = stack[-1]
            if not visV[v]:
                visV[v] = True
            if idx < len(adj[v]):
                u, eid = adj[v][idx]
                stack[-1][3] += 1
                if visE[eid]:
                    continue
                visE[eid] = True
                if not visV[u]:
                    stack.append([u, v, eid, 0])
                else:
                    unpaired[v].append(eid)
            else:
                vec = unpaired[v]
                while len(vec) >= 2:
                    e1 = vec.pop()
                    e2 = vec.pop()
                    u1 = other(e1, v)
                    u2 = other(e2, v)
                    ans.append((u1, v, u2))
                if parent != -1:
                    if vec:
                        e1 = vec.pop()
                        u1 = other(e1, v)
                        ans.append((u1, v, parent))
                    else:
                        unpaired[parent].append(parentEdge)
                stack.pop()

    print(len(ans))
    for u, v, w in ans:
        print(u, v, w)

if __name__ == "__main__":
    solve()