随笔-65  评论-6  文章-0  trackbacks-0
 1 /*
 2 Author:    Leo.W
 3 Descriptipn:    给定几个顶点以及已知某几个顶点存在通路,求最少还需几条路即可完成连通图
 4 How to Do:    由最后一组测试数据易知999 0,且结合最小生成树的知识可得,连通分量数减一即得解
 5   */
 6 #include <iostream>
 7 #include <stdio.h>
 8 #include <string.h>
 9 using namespace std;
10 #define MAXSIZE 1000
11 int path[MAXSIZE][MAXSIZE];
12 bool appear[MAXSIZE];
13 bool chose[MAXSIZE];
14 int m,n,lt;//图中连线后的连通分量数
15 
16 void bfs(int num){
17     chose[num]=true;
18     int i;
19     for(i=1;i<=m;i++)
20         if(i!=num&&path[num][i]==0&&!chose[i]){//点i与点num有连线,并且点i还未被选入集合
21             lt--;    bfs(i);
22         }
23 }
24 int main(){
25     //freopen("in.txt","r",stdin);
26     while(scanf("%d",&m),m){//城镇数
27         scanf("%d",&n);//已有的公路条数
28         lt=m;
29         memset(appear,false,MAXSIZE);
30         memset(chose,false,MAXSIZE);
31         int i,j;
32         for(i=1;i<=m;i++){
33             for(j=1;j<=m;j++)
34                 path[i][j]=MAXSIZE;
35         }
36         for(i=0;i<n;i++){
37             int begin,end;
38             scanf("%d%d",&begin,&end);
39             appear[begin]=appear[end]=true;//表示已经连上线的点,即已经出现
40             path[begin][end]=path[end][begin]=0;
41         }
42         for(i=1;i<=m;i++)
43             if(appear[i]&&!chose[i]){
44                 bfs(i);
45             }
46         printf("%d\n",lt-1);
47     }
48     return 0; 
49 } 
posted on 2012-03-06 13:38 Leo.W 阅读(63) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理