P6279 题解

Overview

结论（待论证）

Description

给定一个有向图，这个有向图的每一个点所连接的点都属于同一个集合。

求集合数量最大且字典序最小的集合标号方案。

Solution

先讲结论。

结论：用 vector 存储每个点所连接的点，从 $1$ 到 $n$ 暴力用并查集按秩合并（要合并 vector 的东西，一层一层的合并下去）。

Proof

先讲复杂度。

时间复杂度 $O(\alpha (n))$。
按秩合并空间复杂度 $O(n)$，vector 的存储的东西的空间被 clear 了，（其实我也不清楚 clear 的原理）所以没事。

再讲正确性。

这里，合并一定会合并到底。

Code

#include <bits/stdc++.h>
#define int long longusing namespace std;int fa[200001], sz[200001];
vector<int> vec[200001];int FindFather(int x){if(fa[x] == x) return x;int tmp = FindFather(fa[x]);sz[x] = sz[fa[x]] + 1;return fa[x] = tmp;
}
void Union(int u, int v){u = FindFather(u), v = FindFather(v);if(u == v) return;if(sz[u] < sz[v]) swap(u, v);sz[u] += sz[v];fa[v] = u;for(int i = 0; i < vec[v].size(); i++)if(vec[u].size()) Union(vec[u][0], vec[v][i]);for(int i = 0; i < vec[v].size(); i++)vec[u].push_back(vec[v][i]);
}signed main(){int n, m; cin >> n >> m;for(int i = 1; i <= n; i++) fa[i] = i;for(int i = 1; i <= m; i++){int u, v; cin >> u >> v;vec[u].push_back(v);}for(int i = 1; i <= n; i++){if(vec[i].size() > 1){for(int j = 0; j < vec[i].size() - 1; j++){Union(vec[i][j], vec[i][j + 1]);}}}map<int, int> mp;int tot = 0;for(int i = 1; i <= n; i++){if(!mp[FindFather(i)]) mp[fa[i]] = ++tot;cout << mp[fa[i]] << endl;}return 0;
}