Union Find トポロジカル クラスカル

重み付きユニオン

```c++

template<class Abel> struct UnionFind {
	vector<int> par;
	vector<int> rank;
	vector<Abel> diff_weight;

	UnionFind(int n = 1, Abel SUM_UNITY = 0) {
		init(n, SUM_UNITY);
	}

	void init(int n = 1, Abel SUM_UNITY = 0) {
		par.resize(n); rank.resize(n); diff_weight.resize(n);
		for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY;
	}

	int root(int x) {
		if (par[x] == x) {
			return x;
		}
		else {
			int r = root(par[x]);
			diff_weight[x] += diff_weight[par[x]];
			return par[x] = r;
		}
	}

	Abel weight(int x) {
		root(x);
		return diff_weight[x];
	}

	bool issame(int x, int y) {
		return root(x) == root(y);
	}

	bool merge(int x, int y, Abel w) {//xのほうがyよりw大きい
		w += weight(x); w -= weight(y);
		x = root(x); y = root(y);
		if (x == y) return false;
		if (rank[x] < rank[y]) swap(x, y), w = -w;
		if (rank[x] == rank[y]) ++rank[x];
		par[y] = x;
		diff_weight[y] = w;
		return true;
	}

	Abel diff(int x, int y) {
		return weight(y) - weight(x);
	}
};
```

ABCでサイズ付きユニオンが出て初めて使った

```c++
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
using Graph = vector<vector<int>>;
ll mypow(ll x, ll n, ll m) {
	if (n == 0) {
		return 1;
	}
	if (n % 2 == 0) {
		return mypow(x*x%m, n / 2, m);
	}
	else {
		return x * mypow(x, n - 1, m) % m;
	}
}
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
const int MAX = 510000;
ll fac[MAX], finv[MAX], inv[MAX];
//テーブルをつくる前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;//mod pにおける1,2,,,nの逆元
	for (int i = 2; i < MAX; ++i) {
		fac[i] = fac[i - 1] * i%INF;
		inv[i] = INF - inv[INF%i] * (INF / i) % INF;
		finv[i] = finv[i - 1] * inv[i] % INF;
	}
}

ll COM(int n, int k) {
	if (n < k)return 0;
	if (n < 0 || k < 0)return 0;
	return fac[n] * (finv[k] * finv[n - k] % INF) % INF;
}
///////////////////////////////////////

struct UnionFind {

	std::vector<int> data;
	// dataの各要素について
	// 負の値:その集合のルートであること示す。また、その絶対値は集合の要素数となっている。
	// 正の値:親ノードの番号(dataのインデックス)。root()を呼び出すたびに集合のルートを指すように書きなおされるので木はそんなに深くならない

	//初期化 size:最大要素数
	UnionFind(int size) : data(size, -1) {}

	// 集合を併合する
	// すでに同じ集合だった場合は、falseが返る
	bool unite(int x, int y) {
		x = root(x);
		y = root(y);
		if (x != y) {
			// 要素数の大きな方へ合併するためのswap
			if (data[y] < data[x]) std::swap(x, y);
			// 要素数を加算する
			data[x] += data[y];
			// yの属する集合のルートをxに変更
			data[y] = x;
		}
		return x != y;
	}

	// 同じ集合かどうか判定
	bool find(int x, int y) {
		return root(x) == root(y);
	}

	// 集合の識別番号を返す
	int root(int x) {
		// 負の値を持つものがその集合のルート
		// 正の値は同じ集合に属するものを指す(辿ればいずれルートへ着く)
		return (data[x] < 0) ? x : data[x] = root(data[x]);
	}

	// 集合の要素数を返す
	int size(int x) {
		return -data[root(x)];
	}
};
vector<int>G[100100];
int g[100100];
int main() {
	int n, m, k; cin >> n >> m >> k;
	UnionFind u(n);
	REP(i, n)g[i] = 0;
	REP(i, m) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		u.unite(a, b);
		G[a].push_back(b);
		G[b].push_back(a);
	}
	REP(i, k) {
		int c, d;
		cin >> c >> d;
		c--, d--;
		if (u.find(c, d)) {
			g[c]++;
			g[d]++;
		}
	}
	REP(i, n) {
		cout << u.size(i) -G[i].size()-g[i]-1<< " ";
	}
	cout << endl;
	return 0;
}
```
仕組みはまだ追えてないけどコンテスト中にネットで見つけて張ることができて良かった

rank(最大深さ)付きunion

```
struct UnionFind {
    vector<int>par;
    vector<int>rank;

    UnionFind(int N) :par(N),rank(N) {
        for (int i = 0; i < N; ++i) {
            par[i] = i;
            rank[i] = 0;
        }
    }

    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;//各木について木の高さ(rank)を記憶しておく
        if (rank[x] < rank[y]) {
            //併合の際に二つの木のrankが異なればrankの小さいものから大きいものへ辺を張る
            par[rx] = ry;
        }
        else {
            par[ry] = rx;
            if (rank[rx] == rank[ry])rank[rx]++;
        }
    }

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

トポロジカルソート

viからvjに辺があるならi>=j
//DAG(有向無閉路グラフ)<=>トポロジカルソートができる
//方法１
//入次数が0の頂点があればその頂点をソート後の結果に追加しその頂点と隣接した頂点の
//入次数を-1するこれを入次数が0の頂点がなくなるまで繰り返すO(V+E)

```c++

vector<int>g[100010];//グラフの隣接リスト
int h[100010];//頂点の入次数を管理
int main() {
	int v, e; cin >> v >> e;
	REP(i, e) {
		int s, t;
		cin >> s >> t;
		g[s].push_back(t);
		h[t]++;
	}
	stack<int>st;
	REP(i, v)if (h[i] == 0)st.push(i);
	//ソートされた後のグラフ
	vector<int>ans;
	while (st.size()) {
		int i = st.top(); st.pop();
		ans.push_back(i);
		for (auto j : g[i]) {
			h[j]--;
			if (h[j] == 0)st.push(j);
		}
	}
	for (int i : ans)cout << i << endl;
	return 0;
}
```

```c++
// 頂点数、変数
int v, e;
const int MAX_N = 10010;
// 隣接リスト
vector<int> g[MAX_N];
bool used[MAX_N];
// トポロジカルソートされた数列
vector<int> ans;

void dfs(int u) {
  if(used[u]) return;
  used[u] = true;
  for(auto& i: g[u]) dfs(i);
  // 帰りがけ順で追加
  ans.push_back(u);
}

void tsort() {
  for(int i=0; i<v; ++i) dfs(i);
  reverse(ans.begin(), ans.end());
}

signed main(void)
{
  cin >> v >> e;
  for(int i=0; i<e; ++i) {
    int s, t;
    cin >> s >> t;
    g[s].push_back(t);
  }

  tsort();
  for(int i: ans) cout << i << endl;

  return 0;
}
```
例題　+bit dp
abc 041 徒競走
トポロジカルソートの数え上げはbitdpでできる。
dp[頂点集合Sをトポロジカルソートする方法の通り数]

```c++

//トポロジカルソートした結果の数列が何通りあるか
int N, M; 
ll ans = 0;
vector<int>g[20];
ll dp[1 << 17];
int main() {
	cin >> N >> M;
	REP(i, M) {
		int x, y; cin >> x >> y;
		x--, y--;
		g[x].push_back(y);
	}
	dp[0] = 1;
	REP(i, 1 << 17)dp[i] = 0;
	dp[0] = 1;
	bool bad[17][17];
	for (int bit = 0; bit < (1 << N); ++bit) {
		for (int j = 0; j < N; ++j) {
			if (!(bit&(1 << j))) {
				bool ok = true;
				for (auto x : g[j]) {
					if ((1 << x)&bit) {
						ok = false;
					}
				}
				if (ok)dp[bit + (1 << j)] += dp[bit];
			}
		}
	}
	cout << dp[(1 << N) - 1] << endl;
	return 0;
}
```
トポロして深さを保存しておくやつ restore the tree

```cpp

for (int i = 0; i < N; ++i) {
		for (int to : G[ans[i]]) {
			dep[to] = max(dep[to], dep[ans[i]] + 1);
		}
	}
	int root = ans[0];
	int res[100100];
	res[root] = -1;
	REP(i, N) {
		for (int j : G[ans[i]]) {
			if (dep[ans[i]] + 1 == dep[j]) {
				res[j] = ans[i];
			}
		}
	}
	REP(i, N) {
		cout << res[i] + 1 << endl;
	}
```
サイズ付きユニオン拾い物

```c++

struct UnionFind {
    vector<int> par;
    vector<int> rank;
    vector<ll> Size;
    UnionFind(int n = 1) {
        init(n);
    }
 
    void init(int n = 1) {
        par.resize(n + 1); rank.resize(n + 1); Size.resize(n + 1);
        for (int i = 0; i <= n; ++i) par[i] = i, rank[i] = 0, Size[i] = 1;
    }
 
    int root(int x) {
        if (par[x] == x) {
            return x;
        }
        else {
            int r = root(par[x]);
            return par[x] = r;
        }
    }
 
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
 
    bool merge(int x, int y) {
        x = root(x); y = root(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;
    }
 
    ll size(int x){
        return Size[root(x)];
    }
};
```

```c++
struct unionfind{
    vector<int> par, sz;
    unionfind() {}
    unionfind(int n):par(n), sz(n, 1){
        for(int i=0; i<n; i++) par[i]=i;
    }
    int find(int x){
        if(par[x]==x) return x;
        return par[x]=find(par[x]);
    }
    void unite(int x, int y){
        x=find(x); y=find(y);
        if(x==y) return;
        if(sz[x]>sz[y]) swap(x, y);
        par[x]=y;
        sz[y]+=sz[x];
    }
    bool same(int x, int y){
        return find(x)==find(y);
    }
    int size(int x){
        return sz[find(x)];
    }
};
```


past グラデーション

```c++

#include<iostream>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<bitset>
#include<functional>
#include<iterator>
#include<complex>
#include<fstream>
#include<random>
#include<ctype.h>
#include<stdio.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using PII = pair<ll, ll>;
using piii = pair<pii, pii>;
using Pi = pair<int, pii>;
using Graph = vector<vector<int>>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
bool check(int x, int y) {
	if (0 <= x && x<55 && 0 <= y && y<55)return true;
	else return false;
}
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
using Graph = vector<vector<int>>;
ll mypow(ll x, ll n, ll m) {
	if (n == 0) {
		return 1;
	}
	if (n % 2 == 0) {
		return mypow(x*x%m, n / 2, m);
	}
	else {
		return x * mypow(x, n - 1, m) % m;
	}
}
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
const double PI=3.14159265358979323846;
const int MAX = 510000;
ll fac[MAX], finv[MAX], inv[MAX];
//テーブルをつくる前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;//mod pにおける1,2,,,nの逆元
	for (int i = 2; i < MAX; ++i) {
		fac[i] = fac[i - 1] * i%INF;
		inv[i] = INF - inv[INF%i] * (INF / i) % INF;
		finv[i] = finv[i - 1] * inv[i] % INF;
	}
}

ll COM(int n, int k) {
	if (n < k)return 0;
	if (n < 0 || k < 0)return 0;
	return fac[n] * (finv[k] * finv[n - k] % INF) % INF;
}
double Euclidean_distance(double x1, double y1, double x2, double y2){
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

///////////////////////////////////////
struct unionfind {
	vector<int> par, sz;
	unionfind() {}
	unionfind(int n) :par(n), sz(n, 1) {
		for (int i = 0; i<n; i++) par[i] = i;
	}
	int find(int x) {
		if (par[x] == x) return x;
		return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x); y = find(y);
		if (x == y) return;
		if (sz[x]>sz[y]) swap(x, y);
		par[x] = y;
		sz[y] += sz[x];
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
	int size(int x) {
		return sz[find(x)];
	}
};
int main() {
	int n, m; cin >> n >> m;
	int x[40], y[40], c[40];
	for (int i = 0; i < n; ++i)cin >> x[i] >> y[i] >> c[i];
	for (int i = 0; i < m; ++i)cin >> x[n + i] >> y[n + i] >> c[n + i];
	const double inf = 1e9;
	double ans = inf;
	for (int i = 0; i < (1 << m); ++i) {
		using Pd = pair<double, pii>;
		vector<Pd>e;
		int popcnt = 0;
		for (int j = 0; j < m; ++j) {
			if (i&(1 << j))popcnt++;
		}
		for (int j = 0; j < n + m; ++j) {
			for (int k = 0; k < j; ++k) {
				double d = Euclidean_distance(x[j], y[j], x[k], y[k]);
				if (j >= n && !(i&(1 << (j - n))))d = inf;
				if (k >= n && !(i&(1 << (k - n))))d = inf;
				if (c[j] != c[k])d *= 10;
				e.push_back({ d,{j,k} });
			}
		}
		sort(e.begin(), e.end());
		int cnt = 0;
		unionfind uf(n + m);
		double s = 0;
		for (auto p : e) {
			if (!uf.same(p.second.first, p.second.second)) {
				uf.unite(p.second.first, p.second.second);
				s += p.first;
				cnt++;
			}
			if (cnt == n + popcnt - 1)break;
		}
		ans = min(ans, s);
	}
	cout << fixed<<setprecision(10)<< ans << endl;
	return 0;
}
```