白駿アルゴリズム17352号:私はみんなの橋になります!
8616 ワード
リンク
https://www.acmicpc.net/problem/17352
sol1)Union Find
それぞれの島は集合で表すことができ、橋はつながっている2つの島の番号を出力しなければならないので、1~n,iがルートと同じように回ると頂点がルートになるので、つなぎ合わせればいいのです.
つまり、ルートノードを見つければいいのです!
https://www.acmicpc.net/problem/17352
sol1)Union Find
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int int64_t
using namespace std;
struct UnionFind {
vector<int> parent, cnt;
UnionFind(int n) : parent(n), cnt(n, 1) {
iota(parent.begin(), parent.end(), 0);
}
int Find(int x) {
return x == parent[x] ? x : parent[x] = Find(parent[x]);
}
bool Union(int a, int b) {
a = Find(a), b = Find(b);
if (a == b) return 0;
if (a > b) swap(a, b);
parent[b] = a;
cnt[a] += cnt[b];
return 1;
}
};
int32_t main(){
fastio;
int N; cin >> N;
UnionFind UF(N + 1);
for(int i = 0; i < N - 2; i++){
int a,b; cin >> a >> b;
UF.Union(a, b);
}
for(int i = 1; i <= N; i++){
if(i == UF.Find(i)) cout << i << ' ';
}
}
Disjoint Setを利用すればいいです.それぞれの島は集合で表すことができ、橋はつながっている2つの島の番号を出力しなければならないので、1~n,iがルートと同じように回ると頂点がルートになるので、つなぎ合わせればいいのです.
つまり、ルートノードを見つければいいのです!
Reference
この問題について(白駿アルゴリズム17352号:私はみんなの橋になります!), 我々は、より多くの情報をここで見つけました https://velog.io/@inwooleeme/백준-알고리즘-17352번-여러분의-다리가-되어-드리겠습니다テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol