求救大佬:鸡玩炸弹人,过了三分之二的案例,大佬帮忙看一下

#include<bits/stdc++.h>

using namespace std;

const int N=100010;

typedef long long LL;

int p[N],sum[N],sum2[N];//sum表示联通块(并查集)内点的数量,sum2表示每个联通块内是否有炸弹(几个无所谓,只要知道他是否为0即可)

int find(int n)

{

if(n!=p[n]) p[n]=find(p[n]);

return p[n];

}

int main()

{

int n,m;

cin>>n>>m;

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

{

sum[i]=1;

p[i]=i;

}

while(m--)

{

int a,b;

cin>>a>>b;

if(find(a)==find(b)) continue;

sum[find(b)]+=sum[find(a)];

p[find(a)]=find(b);

}

int sum3=0;//sum3的意思是总的炸弹数量,若为0即所有连通块无炸弹

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

{

int x;

cin>>x;

sum3+=x;

if(x)

sum2[find(i)]+=x;

}

bool st1[N],st2[N];

LL res=0;

if(sum3==0)

{

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

{

if(!st2[find(i)])

res+=(LL)sum[find(i)]*(LL)sum[find(i)],st2[find(i)]=true;

}

printf("%lld",res);

}

else

{

int ans=0;

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

{

if(!st1[find(i)]&&sum2[find(i)]!=0)

res+=(LL)sum[find(i)]*(LL)sum[find(i)],ans++,st1[find(i)]=true;

}

if(ans==1)

printf("%lld",res);

else

printf("0");

}

}

全部评论
围观一下下
点赞 回复 分享
发布于 2023-01-18 18:12 未知

相关推荐

05-09 12:23
已编辑
华南理工大学 Java
野猪不是猪🐗:给他装的,双九+有实习的能看的上这种厂我直接吃⑨✌们拿它练练面试愣是给他整出幻觉了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务