浙大PAT 1013题 1013. Battle Over Cities

本文主要是介绍浙大PAT 1013题 1013. Battle Over Cities，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

实质就是判断有几个联通子集，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;
}