首页 > 代码库 > Codeforces 755C：PolandBall and Forest（并查集）
Codeforces 755C：PolandBall and Forest（并查集）
http://codeforces.com/problemset/problem/755/C
题意：该图是类似于树，给出n个点，接下来p[i]表示在树上离 i 距离最远的 id 是p[i]，如果距离相等则p[i]是 id 较小的点。
思路：一开始没什么想法，画几分钟图发现不到什么东西，后来想着 i 和 p[i] 有关系，那么就代表 i 和 p[i] 是属于同一棵树，那么不就是并查集了嘛。抱着试一试的心态搞了一下居然过了。
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <string> 7 #include <iostream> 8 #include <stack> 9 #include <map>10 #include <queue>11 #include <set>12 using namespace std;13 typedef long long LL;14 #define N 10001015 #define INF 0x3f3f3f3f16 int fa[N], num[N];17 18 int Find(int x) {19 if(x == fa[x]) return x;20 return fa[x] = Find(fa[x]);21 }22 23 void Merge(int x, int y) {24 x = Find(x), y = Find(y);25 if(x == y) return ;26 fa[x] = y;27 }28 29 int main()30 {31 int n;32 scanf("%d", &n);33 for(int i = 1; i <= n; i++) fa[i] = i;34 for(int i = 1; i <= n; i++) scanf("%d", &num[i]);35 for(int i = 1; i <= n; i++) {36 Merge(i, num[i]);37 }38 int ans = 0;39 for(int i = 1; i <= n; i++) if(fa[i] == i) ans++;40 printf("%d\n", ans);41 return 0;42 }
Codeforces 755C：PolandBall and Forest（并查集）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。