题目

PAT 甲级 1013 Battle Over Cities (25分) 统计连通分量

思路

1 dfs 2 bfs 3 并查集

题解

dfs

易错

1 每次检查都需要重置vis数组 2 每次检查，被占领城市记为已访问，然后再求连通分量个数，比较方便 3 dfs中没有return，退出条件为：访问完一个连通分量中的所有节点

#include <iostream> #include <vector> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int maxn = 1100; int g[maxn][maxn]; int vis[maxn]; int n,m,k,c1,c2,c; void dfs(int v) { vis[v]=1; for(int i=1; i<=n; i++) { if(vis[i]==1||g[v][i]==0)continue; dfs(i); } } int main(int argc,char * argv[]) { // 1 建图 scanf("%d%d%d",&n,&m,&k); for(int i=0; i<m; i++) { scanf("%d%d",&c1,&c2); g[c1][c2]=g[c2][c1]=1; } // 2 check for(int i=0; i<k; i++) { scanf("%d",&c); fill(vis,vis+maxn,0); //易错点，每次检查都需要重置 // 3 统计连通分量 vis[c]=1; //被占领的城市记为已访问 int cnt = 0; for(int j=1; j<=n; j++) { if(vis[j]==0) { cnt++; dfs(j); } } printf("%d\n",cnt-1); } return 0; }

并查集

易错

1 每轮测试，都必须重置father数组 2 并查集并操作时，被占领的城市c关联的边都跳过 3 进行根个数统计时，跳过被占领的城市c

#include <iostream> #include <vector> #include <cstring> #include <queue> #include <algorithm> #include <cmath> #include <set> using namespace std; const int maxn = 1100; int g[maxn][maxn]; int vis[maxn]; int n,m,k,c1,c2,c; int father[maxn]; void init(){ for(int i=0;i<maxn;i++){ father[i]=i; } } int find_f(int x){ int e = x; while(x!=father[x]){ x=father[x]; } while(e!=father[e]){ int tmp = father[e]; father[e]=x; e = tmp; } return x; } void Union(int a,int b){ int af = find_f(a); int bf = find_f(b); if(af<bf)father[b]=a; else father[a]=b; } int main(int argc,char * argv[]) { // 1 建图 scanf("%d%d%d",&n,&m,&k); for(int i=0; i<m; i++) { scanf("%d%d",&c1,&c2); g[c1][c2]=g[c2][c1]=1; } // 2 check for(int i=0; i<k; i++) { scanf("%d",&c); // 3 统计连通分量 init(); for(int u=1;u<=n;u++){ // c关联的边都跳过，其他的边两顶点进行并查集 if(u==c)continue; for(int j=1;j<=n;j++){ if(g[u][j]==0||j==c)continue; Union(u,j); } } set<int> rts; for(int j=1;j<=n;j++){ if(j==c)continue; rts.insert(find_f(j)); } printf("%d\n",rts.size()-1); } return 0; }