起先，队友和我说过并查集，但是看到这道题目的时候我想还是暂时不用，先凭自己的想法做一下的好，所以就自己闷着脑袋开始做了，然后就开始自己的深搜的，反正这个城市给我的的道路我们建好了一个图之后，只要发现这个图里面的一条边的话我们就计算一次，然后累加，最后组成一个连通图的最小边数就是n-1，所以只要拿n-1-累加的边数就可以了啊。。
代码具体如下:
View Code 1 #include<iostream> 2 using namespace std; 3 int f[1002][1002],Count,visit[1002]; 4 int n,m; 5 void dfs(int j) 6 { 7 for(int i=0;i<n;i++) 8 { 9 if(f[j][i]==1&&!visit[i]) 10 { 11 Count++; 12 visit[i]=1; 13 dfs(i); 14 } 15 } 16 } 17 int main() 18 { 19 int s,e; 20 while(scanf("%d",&n)&&n) 21 { 22 scanf("%d",&m); 23 for(int i=0;i<n;i++) 24 { 25 for(int j=0;j<n;j++) 26 { 27 f[i][j]=-1; 28 } 29 visit[i]=0; 30 } 31 Count=0; 32 for(int i=0;i<m;i++) 33 { 34 scanf("%d%d",&s,&e); 35 f[s-1][e-1]=1; 36 f[e-1][s-1]=1; 37 } 38 39 for(int i=0;i<n;i++) 40 { 41 if(!visit[i]) 42 { 43 visit[i]=1; 44 dfs(i); 45 } 46 } 47 printf("%d\n",n-1-Count); 48 } 49 return 0; 50 } 51 第一个代码可能写得有些笨了，所以其实可以看一下下面的代码。 52 通过并查集，每次我们并列两个新的点，那么这条边我们就不用再建了，累加边。按上面的道理，我就不说了。。 53 #include<iostream> 54 using namespace std; 55 int n,m,Count; 56 int father[1002]; 57 int getfather(int i) 58 { 59 if(father[i]==i)return i; 60 return getfather(father[i]); 61 } 62 void combine(int x,int y) 63 { 64 if(getfather(x)==getfather(y))return ; 65 Count++; 66 father[getfather(y)]=x; 67 } 68 int main() 69 { 70 int s,e; 71 while(scanf("%d",&n)&&n) 72 { 73 scanf("%d",&m); 74 Count=0; 75 for(int i=1;i<=n;i++) 76 father[i]=i; 77 for(int i=0;i<m;i++) 78 { 79 scanf("%d%d",&s,&e); 80 combine(s,e); 81 } 82 printf("%d\n",n-1-Count); 83 } 84 return 0; 85 }
转载于:https://www.cnblogs.com/nuoyan2010/archive/2012/09/01/2667102.html
相关资源：JAVA上百实例源码以及开源项目