[关闭]
@zzzc18 2017-08-04T06:54:57.000000Z 字数 705 阅读 1151

WHU403 可删除并查集

并查集


我们记录一下每个元素的编号pid[]
删除时,将删除的点编号变为一个先前未出现的值,fa等于他自己

  1. #include<cstdio>
  2. #include<cstring>
  3. #define MAXN 2000000+9
  4. using namespace std;
  5. int fa[MAXN],pid[MAXN];
  6. int n,ans1,ans2;
  7. int Find(int x){
  8. return fa[x]==x ? x : fa[x]=Find(fa[x]);
  9. }
  10. void merge(int x,int y){
  11. int xx=Find(x);
  12. int yy=Find(y);
  13. fa[xx]=yy;
  14. }
  15. int main(){
  16. while(scanf("%d",&n)!=EOF){
  17. ans1=ans2=0;
  18. int i;
  19. for(i=0;i<=n;i++){
  20. fa[i]=i;
  21. pid[i]=i;
  22. }
  23. while(true){
  24. char opt[2];
  25. int x,y;
  26. scanf("%s",opt);
  27. if(opt[0]=='e')
  28. break;
  29. if(opt[0]=='c'){
  30. scanf("%d%d",&x,&y);
  31. x=pid[x];
  32. y=pid[y];
  33. merge(x,y);
  34. }
  35. if(opt[0]=='d'){
  36. scanf("%d",&x);
  37. pid[x]=++n;
  38. fa[n]=n;
  39. }
  40. if(opt[0]=='q'){
  41. scanf("%d%d",&x,&y);
  42. x=pid[x];
  43. y=pid[y];
  44. int xx=Find(x);
  45. int yy=Find(y);
  46. if(xx==yy)
  47. ans1++;
  48. else
  49. ans2++;
  50. }
  51. }
  52. printf("%d , %d\n",ans1,ans2);
  53. }
  54. return 0;
  55. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注