PAT (Advanced Level) 1013. Battle Over Cities (25)

并查集判断连通性。

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<map>
using namespace std; const int maxn=;
struct Edge
{
int u,v;
}e[maxn*maxn];
int n,m,k;
int f[maxn]; int Find(int x)
{
if(x!=f[x]) return f[x]=Find(f[x]);
return f[x];
} int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=m;i++)
scanf("%d%d",&e[i].u,&e[i].v); for(int i=;i<=k;i++)
{
int id; scanf("%d",&id);
int sz=n-;
for(int j=;j<=n;j++) f[j]=j;
for(int j=;j<=m;j++)
{
if(e[j].u==id) continue;
if(e[j].v==id) continue;
int fx=Find(e[j].u);
int fy=Find(e[j].v);
if(fx!=fy)
{
f[fx]=fy;
sz--;
}
}
printf("%d\n",sz-);
}
return ;
}
上一篇:Error building Player: CommandInvokationFailure: Failed to re-package resources. See the Console for details. ShareSDK 也有这种错误


下一篇:WorldWind源码剖析系列:日志类Log