Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

Codeforces--Books Exchange (hard version)

守功 2019-10-27 11:28:00 阅读数:46 评论数:0 点赞数:0 收藏数:0

题目链接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 = 200005;

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 ;
 }

 

版权声明
本文为[守功]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/sgatbl/p/11746984.html