upc 工作团队 并查集 + 虚父节点
发布日期:2021-09-25 23:57:37 浏览次数:0 分类:技术文章

本文共 2190 字,大约阅读时间需要 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
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y secondusing namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n,m,tot;int p[N],se[N],fp[N];int cnt;int find(int x){    
                
if(x!=p[x]) p[x]=find(p[x]);
return p[x];}int main(){    //
ios::sync_with_stdio(false);//
cin.tie(0);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
p[i]=i,se[i]=1,fp[i]=i;
cnt=n,tot=n;
while(m--)
{    
int op,l,r;
scanf("%d",&op);
if(op==1)
{    
scanf("%d%d",&l,&r);
l=find(fp[l]),r=find(fp[r]);
if(l!=r)
{    
se[r]+=se[l];
se[l]=0;
cnt--;
p[l]=r;
}
}
else if(op==2)
{    
scanf("%d",&l);
int t=find(fp[l]);
if(se[t]==1) continue;
fp[l]=++tot,p[tot]=fp[l];   
se[tot]=1,se[t]--;
cnt++;
}
else if(op==3)
{    
scanf("%d%d",&l,&r); 
if(find(fp[l])==find(fp[r]))
puts("Yes");
else puts("No");
}
else if(op==4)
{    
scanf("%d",&l);
printf("%d\n",se[find(fp[l])]);
}
else printf("%d\n",cnt);
}
return 0;}

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

上一篇:upc 艰难取舍 最长上升子序列
下一篇:最后一次新生赛 B+C+D

发表评论

最新留言

网站不错 人气很旺了 加油
[***.238.104.143]2022年07月07日 14时43分13秒