テーマ4第3題

1.タイトル番号:1003
2.簡単な題意:ある省は都市交通状況を調査し、既存の都市道路統計表を得て、各道路が直接つながっている都市をリストした.省政府の「円滑な工事」の目標は、全省のどの2つの都市間でも交通を実現させることである(ただし、直接的な道路がつながっているとは限らず、互いに間接的に道路を通過すればよい).最低でも何本の道路を建設する必要がありますか?
3.問題を解く構想の形成過程:また1つの最小生成木の問題で、先生はこの問題を話したことがあって、その時言ったのはそして調査集してこの問題を引き出しました.すべての町をNつに分け、Nつの町をすべてつなぐには、少なくともN-1の道路が彼らをつなぐ必要がある.
4.悟り:get√を調べる.
5.ACのコード:
include #include using namespace std; int bing[1003];//ルートノードint find(int a 1){int a=a 1;while(a!=bing[a])a=bing[a];return a;//void merge(int x,int y){int e;int f;e=find(x);f=find(y);if(e!=f){bing[e]=f;    } } int main(){    //freopen("1.txt","r",stdin);     int n,m,x,y,count;     while (cin>>n&&n){         for(int i=0;i<=n;i++)         bing[i]=i;         cin>>m;         for (int j=m;j>0;j--){             cin>>x>>y;             merge(x,y);         }         count=-1;         for (int i=1;i<=n;i++)         if (bing[i]==i)         count++;         cout<原題:
Problem Description
ある省は都市交通状況を調査し、既存の都市道路統計表を得て、各道路が直接つながっている都市をリストした.省政府の「円滑な工事」の目標は、全省のどの2つの都市間でも交通を実現させることである(ただし、直接的な道路がつながっているとは限らず、互いに間接的に道路を通過すればよい).最低でも何本の道路を建設する必要がありますか?

 
Input
テスト入力には、いくつかのテスト例が含まれます.各試験例の第1行は、都市数N(<1000)と道路数Mの2つの正の整数を与える.その後のM行はM道に対応し、各行は正の整数のペアを与え、それぞれこの道が直接つながっている2つの町の番号である.簡単にするために、町は1からN番までです.
注意:2つの都市の間には複数の道路が通じる、すなわち
3
1 2
1 2
2
1
2
このような入力も合法的である
Nが0の場合、入力は終了し、この使用例は処理されない.

 
Output
各試験例について、少なくとも建設が必要な道路数を1行に出力する.

 
Sample Input

   
   
   
   

    
    
    
    4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0

   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    1
0
2
998