• <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){//城鎮數
            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 閱讀(134) 評論(0)  編輯 收藏 引用
            国产精品永久久久久久久久久| 亚洲va久久久噜噜噜久久男同| 日本精品久久久久中文字幕| 久久精品国产一区| 三级片免费观看久久| 9久久9久久精品| 亚洲国产精品嫩草影院久久| 久久99精品国产99久久6男男| 亚洲国产成人精品女人久久久 | 模特私拍国产精品久久| 久久w5ww成w人免费| 亚洲国产精品成人AV无码久久综合影院| 国产激情久久久久久熟女老人| 国产成人精品久久一区二区三区av| 婷婷伊人久久大香线蕉AV| 狠狠综合久久综合中文88| 国内精品久久久久久99蜜桃| 亚洲精品成人网久久久久久| 国产高潮久久免费观看| 国产一区二区三区久久精品| 色欲av伊人久久大香线蕉影院| 久久久久99这里有精品10| 99久久精品免费看国产免费| 国产人久久人人人人爽| 久久综合久久美利坚合众国| 亚洲国产精品一区二区三区久久 | 久久99精品国产一区二区三区| 久久精品国产亚洲AV久| 色综合久久夜色精品国产| 欧美性大战久久久久久| 久久涩综合| 久久香蕉国产线看观看猫咪?v| 91精品国产综合久久香蕉| 成人亚洲欧美久久久久| 狠狠色综合久久久久尤物| 久久久久亚洲精品天堂久久久久久| 99久久精品国产毛片| 久久久久亚洲?V成人无码| 久久精品国产福利国产琪琪| 久久久精品人妻无码专区不卡| 国产精品内射久久久久欢欢 |