CodeForces – 1214D B2. Books Exchange (hard version)
- 2019 年 10 月 28 日
- 筆記
题目链接：http://codeforces.com/problemset/problem/1249/B2
思路：用并查集模拟链表，把关系串联起来，如果成环，则满足题意。之后再用并查集合并一个链，一个链代表
一个集合，一个集合有共同的祖先，一个集合答案相同，则输出答案时候只需要输出该元素属于哪一个集合，那个集合有几个元素
就可以了。
1 #include <stdio.h> 2 #include <iostream> 3 using namespace std; 4 5 const int N = (int)1e5+100; 6 int fa[N]; 7 int ans[N]; 8 int root[N]; 9 10 int search(int x,int& deep){ 11 12 ++deep; 13 if(fa[x] == x) return root[x] = x; 14 else{ 15 return root[x] = search(fa[x],deep); 16 } 17 } 18 19 int main(){ 20 21 int q; 22 scanf("%d",&q); 23 24 int n,in; 25 while(q--){ 26 scanf("%d",&n); 27 28 for(int i = 1; i <= n; i++){ 29 fa[i] = root[i] = i; 30 ans[i] = 0; 31 } 32 33 int deep = 0; 34 for(int i = 1; i <= n; i++){ 35 scanf("%d",&in); 36 deep = 0; 37 if(search(in,deep) == i){ 38 ans[i] = deep; 39 } 40 else fa[i] = in; 41 } 42 43 printf("%d",ans[root[1]]); 44 for(int i = 2; i <= n; i++) printf(" %d",ans[root[i]]); 45 printf("n"); 46 } 47 48 return 0; 49 }
