嗯...

 

题目链接：

 

思路：

　　这道题可以看出是并查集的思想，然后用一个while嵌套一下，输入一条路的两个端点，就将这两个端点合并，表示这两个地方可以互相到达。然后从1到n for 一遍，如果这个点的父亲和它本身相同（即它并没有与其他任何的点并在一起），就将数量+1，注意现在的ans是点的个数，要修的路的个数即为点的个数减一。

 

AC代码：

1 #include
      
        2 #include
       
         3 #include
        
          4  5 using namespace std; 6  7 int f[100005]; 8 int n, m, x, y; 9 10 inline int find(int x){11     if(x != f[x])12         f[x] = find(f[x]);13     return f[x];14 }//"查 "15 16 int main(){17     while(true){18         int ans = 0;19         scanf("%d", &n);20         if(n == 0)21             return 0;//结束 22         scanf("%d", &m);23         for(int i = 1; i <= n; i++)24             f[i] = i;25         for(int i = 1; i <= m; i++){26             scanf("%d%d", &x, &y);27             int r1 = find(x);28             int r2 = find(y);29             if(r1 != r2){30                 f[r1] = r2;31             }//"并"  32         }33         for(int i = 1; i <= n; i++){34             if(find(i) == i){
    //没与任何点并在一起 35                 ans++;//点的个数 36             }37         }38         printf("%d\n", ans - 1);//要修的路的条数 39     }40     return 0;41 }