本文共 2186 字，大约阅读时间需要 7 分钟。

问题 A: 工作团队

时间限制: 1 Sec 内存限制: 128 MB

题目描述

一家公司有n名员工，刚开始每个人单独构成一个工作团队。 有时一项工作仅凭一个人或一个团队难以完成，所以公司会让某两个人所在的团队合并。 但有的工作属于闷声大发财类型的，不适合多人做，所以公司有时也会让一个人从他当前所在的团队中分离出来，构成单独的团队。 公司也要对当前团队的情况进行了解，所以他们也会询问一些问题，比如某两个人是否属于同一工作团队，某个人所在的团队有多少个人，或者当前一共有多少个工作团队。 作为该公司的软件服务商，你的任务便是实现一个实时的操作和查询系统。 输入 每个测试点第一行有两个正整数n ,m ，表示员工数和公司的指令数。 接下来m 行，每行的格式为下列所述之一： 1 u v ，表示将第u个人与第v个人所在的团队合并，如果两个人所在团队相同，则不执行任何操作。 2 w，表示使第w个人从当前的团队中分离出来，如果第w个人不在任何多人团队中，则不执行任何操作。 3 x y ，表示询问x ,y两个人是否在同一个工作团队，是的话回答Yes，否则回答No。 4 z，表示询问第z个人所在的工作团队一共有多少个人。 5，询问当前一共有多少个工作团队。 输出 对每个询问输出一行相应的值表示答案。 样例输入 Copy 3 11 1 1 2 3 2 3 4 2 1 2 3 3 2 3 4 2 5 2 2 3 2 3 4 2 5 样例输出 Copy No 2 Yes 3 1 No 1 2 提示 对于100%的数据，均有1≤n≤50000,1≤m≤100000

一个标准的并查集的题，信息也是比较好维护的，开一个se数组存每个集合的数量，合并的时候 团队 – ， 分裂的时候 团队 ++ 。有点难度的话就是怎么样删除一个结点而不影响并查集的结构。显然直接删是删不去的，假如删的是一个集合的跟，也就是 p [ i ] = i 的点，那么以这个点为根点都会受影响，所以肯定是不能直接删掉的。那么可以考虑建立一个虚父节点 fp[N] ，每当查询一个数 x 的时候，都把它映射成 fp [ x ] ，通过这样，就可以保证根节点还存在，删根节点的时候，只需要将其虚父节点改成 tot++ ，再将 p [ tot ] = tot 即可，tot 应该是大于n的数，不能跟原来的冲突，通过这样的处理，当查询根节点的时候，就会映射到 tot ，而查询原来跟根节点在一个集合中的元素的时候，还是会 find 到根节点，完美解决问题。

注意 tot 可能加很多，所以数组要开大点，开小了会超内存？(反正我超了两次。。)

寒假训练的时候做过相似的题：Junk-Mail Filter HDU - 2473

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
      
     
    
   

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/105799415 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！