1 /* 2     并查集（Union-Find）裸题 3     并查集三个函数：初始化Init，寻找根节点Find，连通Union 4     考察：连通边数问题 5 */ 6 #include 
     
       7 #include 
      
        8 #include 
       
         9 #include 
        
         10 using namespace std;11 12 const int MAX_N = 1000 + 10;13 int pre[MAX_N];14 int tot;15 16 int find(int root)17 {18     int son, tmp;19     son = root;20 21     while (root != pre[root])22     {23         root = pre[root];24     }25     while (son != root)        //路径压缩    非递归版26     {27         tmp = pre[son];28         pre[son] = root;29         son = tmp;30     }31 32     return root;33 }34 35 void joint(int root1, int root2)36 {37     int x, y;38 39     x = find (root1);40     y = find (root2);41 42     if (x != y)43     {44         pre[x] = y;45         tot--;            //连通一条少一条边46     }47 }48 49 int main(void)        //HDOJ 1232 畅通工程50 {51     //freopen ("inA.txt", "r", stdin);52     int n, m;53     int x, y;54 55     while (~scanf ("%d%d", &n, &m) && n)56     {57         for (int i=1; i<=n; ++i)58         {59             pre[i] = i;60         }61         tot = n - 1;        //tot 记录边 （n个顶点有n-1条边）62         while (m--)63         {64             scanf ("%d%d", &x, &y);65             joint (x, y);66         }67         printf ("%d\n", tot);        //还有几条边（路）没有连通68     }69 70     return 0;71 }