实质就是判断有几个联通子集,400ms的时限。可以用BFS或者DFS或者并查集,效率当然是并查集最高。
我用BFS暴力320ms过了,练习了C++ STL的QUEUE,代码如下:
#include<iostream> #include<queue> using namespace std; int rel[1005][1005]; int main(){ int i,j,k,N,M,K; int from,to,occ; int vst[1005]; cin>>N>>M>>K; for(i=1;i<=N;i++){ for(j=1;j<=N;j++){ rel[i][j]=0; } } for(i=1;i<=M;i++){ cin>>from>>to; rel[from][to]=rel[to][from]=1; } for(i=1;i<=K;i++){ cin>>occ; for(j=1;j<=N;j++){ vst[j]=0; } vst[occ]=1; int cnt=0; for(j=1;j<=N;j++){ if(!vst[j]){ vst[j]=1; cnt++; queue<int>q; q.push(j); while(!q.empty()){ int tmp=q.front(); q.pop(); for(k=1;k<=N;k++){ if(!vst[k]&&rel[tmp][k]){ vst[k]=1; q.push(k); } } } } } cout<<cnt-1<<endl; } return 0; }
DFS,150ms暴力通过
#include<stdio.h> #define max_city 1005 int map[max_city][max_city],mark[max_city]; int n,m,k,repair_city,destroy_city; void dfs(int cur){ int i; for(i=1;i<=n;i++){ if(map[cur][i]&&cur!=destroy_city&i!=destroy_city&&!mark[i]){ mark[i]=1; dfs(i); } } } int main(){ int i,j; int from,to,city; scanf("%d %d %d",&n,&m,&k); for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ map[i][j]=0; } } for(i=0;i<m;i++){ scanf("%d %d",&from,&to); map[from][to]=map[to][from]=1; } while(k){ scanf("%d",&destroy_city); repair_city=0; for(i=1;i<=n;i++){ mark[i]=0; } for(i=1;i<=n;i++){ if(!mark[i]&&i!=destroy_city){ repair_city++; } dfs(i); } printf("%d\n",repair_city-1); k--; } }
而用并查集100ms通过,代码如下:
#include<stdio.h> #define MAXN 1000 #define MAXE MAXN*(MAXN+1)/2 struct Node{ int from; int to; }node[MAXE]; int fat[MAXN],siz[MAXN]; int getfat(int x){ if(fat[x]==x) return x; else return fat[x]=getfat(fat[x]); } void Union(int a,int b){ int fa=getfat(a); int fb=getfat(b); if(fa!=fb){ if(siz[fa]<=siz[fb]){ fat[fa]=fb; siz[fb]+=siz[fa]; } else{ fat[fb]=fa; siz[fa]+=siz[fb]; } } } int main(){ int i,j,cut; int n,m,k; scanf("%d %d %d",&n,&m,&k); for(i=0;i<m;i++){ scanf("%d %d",&node[i].from,&node[i].to); } for(i=0;i<k;i++){ for(j=1;j<=n;j++){ fat[j]=j; siz[j]=1; } scanf("%d",&cut); for(j=0;j<m;j++){ if(node[j].from==cut||node[j].to==cut) continue; if(fat[node[j].from]==fat[node[j].to]) continue; Union(node[j].from,node[j].to); } int cnt=0; for(j=1;j<=n;j++){ if(j!=cut&&fat[j]==j){ cnt++; } } printf("%d\n",cnt-1); } return 0; }