很直接的并查集，只需要找到有多少根，就是需要修的路。
#include<cstdio> #define Max 1010 int root[Max]; int union_find(int x) { return x == root[x] ? x : (root[x] = union_find(root[x])); } int main() { // freopen("in.txt","r",stdin); int sum,n; while(scanf("%d",&sum) != EOF && sum != 0){ scanf("%d",&n); for(int i = 1;i <= sum; i++) root[i] = i; int u,v; for(int i = 0;i < n; i++){ scanf("%d%d",&u,&v); int _u = union_find(u); int _v = union_find(v); if(_u != _v) root[_u] = _v; } int ans = -1; for(int i = 1;i <= sum; i++) if(root[i] == i) ans++; printf("%d\n",ans); } return 0; }并查集：查找和合并。
分开写更直观。
#include<cstdio> #define Max 1010 int root[Max]; int Find(int x) { while(x != root[x]) x = root[x]; return x; } void Union(int x,int y) { int _u = Find(x); int _v = Find(y); if(_u != _v) root[_u] = _v; } int main() { // freopen("in.txt","r",stdin); int sum,n; while(scanf("%d",&sum) != EOF && sum != 0){ scanf("%d",&n); for(int i = 1;i <= sum; i++) root[i] = i; int u,v; for(int i = 0;i < n; i++){ scanf("%d%d",&u,&v); Union(u,v); } int ans = -1; for(int i = 1;i <= sum; i++) if(root[i] == i) ans++; printf("%d\n",ans); } return 0; }当然，在合并的时候不知道，那个根所在的树的节点多，所以要优化。 但是时间上并没有变化，不知道为什么。
#include<cstdio> #include<cstring> #define Max 1010 int root[Max]; int sum[Max]; int visit[Max]; int Find(int x) { while(x != root[x]) x = root[x]; return x; } void Union(int x,int y) { int _u = Find(x); if(visit[x] == 0) sum[_u]++; int _v = Find(y); if(visit[x] == 0) sum[_v]++; if(_u != _v){ if(sum[_v] > sum[_u]){ root[_u] = _v; sum[_v] += sum[_u]; } else { root[_v] = _u; sum[_u] += sum[_v]; } } } int main() { // freopen("in.txt","r",stdin); int s,n; while(scanf("%d",&s) != EOF && s != 0){ memset(visit,0,sizeof(visit)); memset(sum,0,sizeof(sum)); scanf("%d",&n); for(int i = 1;i <= s; i++) root[i] = i; int u,v; for(int i = 0;i < n; i++){ scanf("%d%d",&u,&v); visit[u] = true; visit[v] = true; Union(u,v); } int ans = -1; for(int i = 1;i <= s; i++) if(root[i] == i) ans++; printf("%d\n",ans); } return 0; }