Codeforces--Books Exchange (hard version)

题目链接http://codeforces.com/contest/1249/problem/B2 。并查集思想，将数分成多个集合，每个集合的大小就是一轮的所需天数。

Map[i]存储数据。

flag[i]来表示第i个数是否被访问过。

mm[i]记录第i个集合所对应的集合大小，索引i为第i个集合的根对应的值。

getParent方法利用递归的思想更新每个节点的上继，直接指向当前集合的根。

由于访问过的集合不再进行访问，因此，分析时间复杂度，准确是O(CN)，C为一个常数。在这里需要注意的是，mm在每次使用后要清，不然会有问题。

 #include<bits/stdc++.h>

 /*

 * 并查集

 */

 using namespace std;

 static const int MAX = ;

 int Map[MAX];

 bool flag[MAX];

 map<int, int> mm;

 int getParent(int x){

     if(!flag[x]){

         flag[x] = true;

         Map[x] = getParent(Map[x]);

     }

     return Map[x];

 }

 int main(){

     int q;

     scanf("%d", &q);

     while(q--){

         int n;

         scanf("%d", &n);

         for(int i=;i<=n;i++){

             flag[i] = false;

         }

         // construct set

         int tmp;

         for(int i=;i<=n;i++){

             scanf("%d", &Map[i]);

         }

         // solve

         for(int i=;i<=n;i++){

             int parent = getParent(i);

             mm[parent]++;

         }   

         for(int i=;i<=n;i++){

             if(i==){

                 printf("%d", mm[Map[i]]);

             }

             else{

                 printf(" %d", mm[Map[i]]);

             }

         }

         printf("\n");

         mm.clear();

     }

     return ;

 }

巴特西

Codeforces--Books Exchange (hard version)

最新文章

热门文章