Codeforces–Books Exchange (hard version)
- 2019 年 10 月 27 日
- 笔记
题目链接http://codeforces.com/contest/1249/problem/B2 。并查集思想，将数分成多个集合，每个集合的大小就是一轮的所需天数。
Map[i]存储数据。
flag[i]来表示第i个数是否被访问过。
mm[i]记录第i个集合所对应的集合大小，索引i为第i个集合的根对应的值。
getParent方法利用递归的思想更新每个节点的上继，直接指向当前集合的根。
由于访问过的集合不再进行访问，因此，分析时间复杂度，准确是O(CN)，C为一个常数。在这里需要注意的是，mm在每次使用后要清，不然会有问题。
1 #include<bits/stdc++.h> 2 3 /* 4 * 并查集 5 */ 6 7 using namespace std; 8 9 static const int MAX = 200005; 10 11 int Map[MAX]; 12 bool flag[MAX]; 13 map<int, int> mm; 14 15 int getParent(int x){ 16 if(!flag[x]){ 17 flag[x] = true; 18 Map[x] = getParent(Map[x]); 19 } 20 return Map[x]; 21 } 22 23 int main(){ 24 int q; 25 scanf("%d", &q); 26 while(q--){ 27 int n; 28 scanf("%d", &n); 29 for(int i=1;i<=n;i++){ 30 flag[i] = false; 31 } 32 33 // construct set 34 int tmp; 35 for(int i=1;i<=n;i++){ 36 scanf("%d", &Map[i]); 37 } 38 39 // solve 40 for(int i=1;i<=n;i++){ 41 int parent = getParent(i); 42 mm[parent]++; 43 } 44 45 for(int i=1;i<=n;i++){ 46 if(i==1){ 47 printf("%d", mm[Map[i]]); 48 } 49 else{ 50 printf(" %d", mm[Map[i]]); 51 } 52 } 53 printf("n"); 54 mm.clear(); 55 } 56 return 0; 57 }
