题解 | #畅通工程#
畅通工程
http://www.nowcoder.com/practice/4878e6c6a24e443aac5211d194cf3913
【并查集求极大连通子图数量】
i==getRoot(i)的数量就是极大连通图的数量
再-1就是最少还需几条路
#include<iostream>
using namespace std;
int parent[1000];
void init(int n){
for(int i=0;i<n;i++){
parent[i] = i;
}
}
int getRoot(int i){
while(parent[i]!=i){
i = parent[i];
}
return i;
}
void unionTree(int a,int b){
int root_a = getRoot(a);
int root_b = getRoot(b);
parent[root_a] = root_b;
}
int main(){
int nodes,edges;
int a,b;
while(cin>>nodes>>edges){
if(nodes==0&&edges==0) break;
init(nodes);
for(int i=0;i<edges;i++){
cin>>a>>b;
unionTree(a,b);
}
int counter = 0;
for(int i=0;i<nodes;i++){
if(i==getRoot(i)) counter++;
}
cout<<counter-1<<endl;
}
return 0;
}
