• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆-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){//城鎮(zhèn)數
            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 閱讀(127) 評論(0)  編輯 收藏 引用
            久久精品无码一区二区三区免费| 伊人久久大香线蕉亚洲| 国产精品成人精品久久久| 久久精品国产黑森林| 中文字幕久久精品| 精品无码久久久久久午夜| 色综合合久久天天综合绕视看| 日本久久中文字幕| 久久婷婷色综合一区二区| 久久久亚洲欧洲日产国码二区| 久久99精品国产| 久久久亚洲裙底偷窥综合| 狠狠干狠狠久久| 国产aⅴ激情无码久久| 亚洲国产精品久久久久婷婷软件 | 久久最新免费视频| 久久国语露脸国产精品电影| 99久久免费国产精品热| 国产激情久久久久久熟女老人 | 91精品国产91热久久久久福利| 一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区 | 久久免费视频网站| 无码人妻久久一区二区三区免费丨| 91精品国产91久久| 久久丫精品国产亚洲av不卡| 久久午夜无码鲁丝片秋霞| 国产69精品久久久久9999| 蜜臀av性久久久久蜜臀aⅴ| 香蕉久久夜色精品国产尤物| 久久精品国产精品亚洲下载| 久久精品国产亚洲AV无码偷窥| 欧美精品国产综合久久| 久久天天躁狠狠躁夜夜av浪潮| 99久久夜色精品国产网站| 久久r热这里有精品视频| 国产精品欧美久久久天天影视 | 久久人妻AV中文字幕| 久久精品中文字幕一区| 亚洲欧洲精品成人久久曰影片| 久久久精品久久久久久| 狠狠色综合网站久久久久久久|