AtCoder蟻本 初級編 2-4 データ構造 ③食物連鎖 (POJ No.1182)

Union-Find木に関する問題集です。

ATC001 B - Union Find

B: Union Find - AtCoder Typical Contest 001 | AtCoder

概要

(Union-Find木そのまま)

解答

Submission #4827269 - AtCoder Typical Contest 001 | AtCoder

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
// union-find tree with size(struct)
struct UnionFind {
    vector<int> par; // 親ノード
    vector<int> rank; // ランク
	vector<int> size; // 連結成分のサイズ
 
    UnionFind(int n = 1) {
        init(n);
    }
 
    void init(int n = 1) {
        par.resize(n);
		rank.resize(n);
		size.resize(n);
        for (int i = 0; i < n; ++i){
			par[i] = i;
			rank[i] = 0;
			size[i] = 1;
		}
    }
 
    int find(int x) {
        if (par[x] == x)  return x;
 
        int r = find(par[x]);
        return par[x] = r;
    }
 
    bool issame(int x, int y) {
        return find(x) == find(y);
    }
 
    bool unite(int x, int y) {
	    x = find(x);
		y = find(y);
	    if (x == y) return false;
 
	    if (rank[x] < rank[y]) swap(x, y);
	    if (rank[x] == rank[y]) ++rank[x];
	    par[y] = x;
		size[x] += size[y];
	    return true;
    }
 
	int getSize(int x){
		return size[find(x)];
	}
 
	int getRank(int x){
		return rank[find(x)];
	}
};
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N, Q;
	cin >> N >> Q;
 
	UnionFind uf(N);
	rep(i, Q){
		int p, a, b;
		cin >> p >> a >> b;
		if(p == 0){
			uf.unite(a, b);
		}else if(p == 1){
			cout << (uf.issame(a, b) ? "Yes" : "No") << endl;
		}
	}
}

ARC097 D - Equals

D - Equals

概要

1からNまでの整数を並べ替えた順列pと、1からNまでの整数のM個のペアである(x, y)が与えられる。
下記の操作を好きなだけ行うとき、pi = i となるiの個数の最大値を求めよ.

• 1 ≦ i ≦ M を選び、pxiとpyiをスワップする

方針

1からNまでの頂点がある無向グラフを考え、(pxi, pyi)で各頂点を結んでいく。
このとき同一の連結成分にある頂点同士は自由に頂点値を交換できるため、
各iについて、iとp[i]が同一の連結成分にあれば、pi=iを実現できる。
よってそのようなiの個数を数えてゆけばよい。

解答

Submission #4881954 - AtCoder Regular Contest 097

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
// union-find tree
 
const int max_n = 100005;
 
int par[max_n];
int rnk[max_n];
 
void init(int n){
	rep(i,n){
		par[i+1] = i+1;
		rnk[i+1] = 0;
	}
}
 
// find root of tree with x
int find(int x){
	if(par[x] == x) return x;
	else return par[x] = find(par[x]);
}
 
void unite(int x, int y){
	x = find(x);
	y = find(y);
	if(x == y) return;
 
	if(rnk[x] < rnk[y]) par[x] = y;
	else{
		par[y] = x;
		if(rnk[x] == rnk[y]) rnk[x]++;
	}
}
 
bool same(int x, int y){
	return find(x) == find(y);
}
 
// end union-find tree
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int n,m;
	cin >> n >> m;
 
	int p[n+1];
	rep(i,n) cin >> p[i+1];
 
	init(n);
 
	rep(i,m){
		int x, y;
		cin >> x >> y;
		unite(x,y);
	}
 
	int ans = 0;
	rep(i,n){
		if(same(i+1,p[i+1])){
			ans++;
		}
	}
 
	cout << ans << endl;
}