Help us understand the problem. What is going on with this article?

# Union-Find

Union-Findの解説

## 問題

### DSL_1_A - 互いに素な集合

C++
```#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cctype>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

class UnionFind{
private:
vector<int> par_;

public:
UnionFind(int N) : par_(N){
rep(i, N) par_[i] = i;
}

int root(int x){
if(par_[x] == x) return x;
return root(par_[x]);
}

void unite(int x, int y){
int rx = root(x);
int ry = root(y);

if(rx == ry) return;
par_[rx] = ry;
}

bool same(int x, int y){
int rx = root(x);
int ry = root(y);
return rx == ry;
}
};

int main(int argc, const char * argv[]) {
int n, q;
cin >> n >> q;

UnionFind uni(n);

rep(i, q){
int cmd, x, y;
cin >> cmd >> x >> y;

if(cmd == 0) uni.unite(x, y);
else if(cmd == 1){
if(uni.same(x, y)) cout << 1 << endl;
else  cout << 0 << endl;
}
}

return 0;
}
```

### C - Bridge

Mの要素の一つを使うのをやめる（辺を取り除く）時、他の頂点と辺が連結していない（自身が親要素である）ならば橋である。

C++
```#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

class UnionFind{
vector<int> par_;

public:
UnionFind(int N) : par_(N){
rep(i, N) par_[i] = i;
}

int root(int x){
if(par_[x] == x) return x;
return par_[x] = root(par_[x]);
}

void unite(int x, int y){
int rx = root(x);
int ry = root(y);

if(rx == ry) return;
par_[rx] = ry;
}

bool same(int x, int y){
int rx = root(x);
int ry = root(y);
return rx == ry;
}
};

int main(int argc, const char * argv[]) {
int n, m;
cin >> n >> m;

vector<P> v(m);
rep(i, m){
cin >> v[i].first >> v[i].second;
v[i].first--;
v[i].second--;
}

int res=0;
rep(i, m){
UnionFind uni(n);
rep(j, m){
if(i != j && !uni.same(v[j].first, v[j].second)){
uni.unite(v[j].first, v[j].second);
}
}
set<int> s;
rep(j, n){
if(uni.root(j) == j) s.insert(j);
}
if(s.size()>1) res++;
}
cout << res << endl;
return 0;
}
```

### D - Friends

ルートの配列の要素に-1の負の数を加算していきグループ人数をカウントしていきます。

サイズ取得時に正の数に変換します。

C++
```#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

class UnionFInd{
vector<int> par_;
public:
UnionFInd(int n):par_(n){
rep(i, n) par_[i] = -1;
}

int root(int x){
if(par_[x] < 0) return x;
return par_[x] = root(par_[x]);
}

bool unite(int x, int y){
int rx = root(x);
int ry = root(y);

if(rx == ry) return false;
if (par_[rx] > par_[ry]) swap(rx, ry);
par_[rx] += par_[ry];
par_[ry] = rx;
return true;
}

bool same(int x, int y){
int rx = root(x);
int ry = root(y);
return rx == ry;
}

int size(int x){
return -par_[root(x)];
}
};

int main(int argc, const char * argv[]) {
int n, m;
cin >> n >> m;

UnionFInd uni(n);
rep(i, m){
int a, b;
cin >> a >> b;
a--;
b--;
uni.unite(a, b);
}
int res = 0;
for (int i=0; i<n; i++) res = max(res, uni.size(i));
cout << res << endl;

return 0;
}
```
エンジニア。 c/c++、pythonをメインで記述しています。
Why not register and get more from Qiita?
1. We will deliver articles that match you
By following users and tags, you can catch up information on technical fields that you are interested in as a whole
2. you can read useful information later efficiently
By "stocking" the articles you like, you can search right away