작업 중...
여기서 유니온 파인드 템플릿을 먼저 제공합니다.
다음은 일반적으로 사용되는 두 가지 형태입니다.
경로 압축
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