유니온 파인드 - 강의 내용 보완 (진행 중)

작업 중...

여기서 유니온 파인드 템플릿을 먼저 제공합니다.

다음은 일반적으로 사용되는 두 가지 형태입니다.

경로 압축

int parent[MAXN], n, m;
void init() {
    for(int i = 1; i <= n; i++) parent[i] = i;
}
int root(int x) {
    if(x != parent[x]) parent[x] = root(parent[x]);
    return parent[x];
}
void unite(int x, int y) {
    int rx = root(x), ry = root(y);
    if(rx != ry) parent[rx] = ry;
}

가중치 유니온 파인드

int root(int x) {
    if(x == parent[x]) return x;
    else {
        int temp = parent[x];
        parent[x] = root(parent[x]);
        dist[x] += dist[temp];
        return parent[x];
    }
}
void unite(int x, int y, int value) {
    int rx = root(x), ry = root(y);
    if(rx != ry) {
        parent[rx] = ry;
        dist[rx] = dist[y] - dist[x] + value;
    }
}

후속 문제

A. 포켓몬 대결

HZNUOJ -- 포켓몬 결투

해법: 가중치 유니온 파인드를 활용하여 가중치를 3으로 나눈 나머지를 저장하고, 최종적으로 상성 관계를 판단합니다.

구현 코드 (오래된 버전이므로 참고용)

#include <iostream>
#include <cstdio>
using namespace std;
int parent[100000], dist[100000];
int root(int x) {
    if(x != parent[x]) {
        int temp = parent[x];
        parent[x] = root(parent[x]);
        dist[x] = (dist[x] + dist[temp]) % 3;
    }
    return parent[x];
}
void unite(int x, int y) {
    int rx = root(x), ry = root(y);
    if(rx != ry) {
        parent[rx] = ry;
        dist[rx] = (dist[y] - dist[x] + 1) % 3;
    }
}
int main() {
    int n, t, i, x, y;
    scanf("%d %d", &n, &t);
    for(i = 1; i <= n; i++)
        parent[i] = i;
    while(t--) {
        scanf("%d %d", &x, &y);
        unite(x, y);
    }
    scanf("%d %d", &x, &y);
    root(x); root(y);

    if(dist[x] - dist[y] == 1 || dist[x] - dist[y] == -2)
        cout << "wait for me, my dear!" << endl;
    else if(dist[x] == dist[y])
        cout << "can I win the game?" << endl;
    else
        cout << "change! change! change!" << endl;
}

View CodeB. 뿌리 식물

해법: 유니온 파인드로 연결된 컴포넌트들을 하나로 묶고, 최종적으로 루트 노드의 개수를 세어 반환합니다.

#include <bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 2e6 + 7;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
int parent[MAXN], n, m;
void init() {
    for(int i = 1; i <= (n * m); i++) parent[i] = i;
}
int root(int x) {
    if(x != parent[x]) parent[x] = root(parent[x]);
    return parent[x];
}
void unite(int x, int y) {
    int rx = root(x), ry = root(y);
    if(rx != ry) parent[rx] = ry;
}
void solve() {
    cin >> n >> m;
    init();
    int q; cin >> q;
    while(q--) {
        int u, v; cin >> u >> v;
        unite(u, v);
    }
    int answer = 0;
    for(int i = 1; i <= n * m; i++) {
        if(root(i) == i) answer++;
    }
    cout << answer;
}
signed main() {
    solve();
}

View CodeC. 도로 복구

최소 신장 트리를 이해한 후에 접근하는 것을 권장합니다.

해법: 매번 가장 빠른 연결을 선택하여 병합하고, 더 이상 병합할 수 없을 때 마지막 병합 시간을 출력합니다.

#include <bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 3e5 + 7;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
int parent[MAXN], n, m;
struct Edge {
    int u, v, w;
} edges[MAXN];
bool cmp(Edge a, Edge b) {
    return a.w < b.w;
}
void init() {
    for(int i = 1; i <= n; i++) parent[i] = i;
}
int root(int x) {
    if(x != parent[x]) parent[x] = root(parent[x]);
    return parent[x];
}
void unite(int x, int y) {
    int rx = root(x), ry = root(y);
    if(rx != ry) parent[rx] = ry;
}
void solve() {
    cin >> n >> m;
    init();
    for(int i = 1; i <= m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }
    sort(edges + 1, edges + 1 + m, cmp);
    int result = 0, count = 0;
    for(int i = 1; i <= m; i++) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        if(root(u) != root(v)) {
            unite(u, v);
            result = max(result, w);
        }
    }
    for(int i = 1; i <= n; i++) {
        if(root(i) == i) count++;
    }
    if(count > 1) cout << "-1";
    else cout << result;
}
signed main() {
    solve();
}

View Code

태그: 유니온파인드 알고리즘 데이터구조 경로압축 가중치유니온파인드

10월 13일 09:31에 게시됨