HDU1213 How Many Tables （并查集）

题目大意：

　　有一个人要过生日了，请他的朋友来吃饭，但是他的朋友互相认识的才能坐在一起，朋友的编号从1 ~ n,输入的两个数代表着这两个人互相认识（如果1和2认识，2和3认识，那么1和3也就认识了）。问需要多少桌子。

思路：

　　并查集的基础题目，pre数组存的是父节点的值，root数组代表是否为根节点。最后统计根节点的数量就可以了~~~~~

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <cmath>

 #include <cctype>

 #include <algorithm>

 using namespace std;

 const int MAXN = 1e3 + ;

 int pre[MAXN];

 bool root[MAXN];

 int Find(int x)

 {

     int r = x;

     while(pre[r] != r)

     {

         r = pre[r];

     }

     int i = x,j;

     while(pre[i] != r) //路径压缩

     {

         j = i;

         i = pre[i];

         pre[j] = r;

     }

     return r;

 }

 void mix(int a,int b)

 {

     int x = Find(a);

     int y = Find(b);

     if(x > y)

     {

         pre[x] = y;

     }

     if(x < y)

     {

         pre[y] = x;

     }

 }

 int main()

 {

     int t;

     scanf("%d",&t);

     while(t--)

     {

         int M,N;

         for(int i = ; i <= MAXN; i++)

         {

             pre[i] = i;

             root[i] = false;

         }

         scanf("%d%d",&M,&N);

         while(N--)

         {

             int a,b;

             scanf("%d%d",&a,&b);

             mix(a,b);

         }

         for(int i = ; i <= M; i++)

         {

             if(pre[i] == i)

                root[i] = true;

         }

         int ans = ;

         for(int i = ; i <= M; i++)

         {

             if(root[i]) ans ++;

         }

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

HDU1213 How Many Tables （并查集）

最新文章

热门文章