POJ-1182 食物链---并查集（附模板）

题目链接：

https://vjudge.net/problem/POJ-1182

题目大意：

中文题，不多说。

思路：

给每个动物创建3个元素，i-A, i-B, i-C

i-x表示i属于种类x，并查集每个组表示组内元素同时发生或者同时不发生

举例说明，

对于x和y属于同一组，合并x和y，合并x+n和 y+n，合并x+2n和y+2n，这里需要判断x和y+n是否是同一组，x和y+2n是否是同一组，如果是的话那就表示出错。

对于x吃y，合并x和y+n，x+n和y+2n，x+2n和y。这里需要判断x和y，x和y+2n是否是同一类

并查集模板：

 //初始化n个元素

 void init(int n)

 {

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

     {

         par[i] = i;

         high[i] = ;

     }

 }

 //查询树的根

 int Find(int x)

 {

     return par[x] == x ? x : par[x] = Find(par[x]);//路径压缩

 }

 void unite(int x, int y)

 {

     x = Find(x);

     y = Find(y);

     if(x == y)return;

     if(high[x] < high[y])par[x] = y;//y的高度高，将x的父节点设置成y

     else

     {

         par[y] = x;

         if(high[x] == high[y])high[x]++;

     }

 }

 bool same(int x, int y)

 {

     return Find(x) == Find(y);

 }

题解：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<stack>

 #include<map>

 #include<sstream>

 using namespace std;

 typedef long long ll;

 const int maxn = 1e6 + ;

 const int INF =  << ;

 int dir[][] = {,,,,-,,,-};

 int T, n, m, x;

 int high[maxn];//树的高度

 int par[maxn];//父节点

 //初始化n个元素

 void init(int n)

 {

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

     {

         par[i] = i;

         high[i] = ;

     }

 }

 //查询树的根

 int Find(int x)

 {

     return par[x] == x ? x : par[x] = Find(par[x]);//路径压缩

 }

 void unite(int x, int y)

 {

     x = Find(x);

     y = Find(y);

     if(x == y)return;

     if(high[x] < high[y])par[x] = y;//y的高度高，将x的父节点设置成y

     else

     {

         par[y] = x;

         if(high[x] == high[y])high[x]++;

     }

 }

 bool same(int x, int y)

 {

     return Find(x) == Find(y);

 }

 int main()

 {

     //std::ios::sync_with_stdio(false);

     cin >> n >> m;

     init(n * );

     //每个元素用x， x + n, x + 2 * n

     int c, x, y, ans = ;

     while(m--)

     {

         scanf("%d%d%d", &c, &x, &y);

         x--;//把输入变成0到n-1的下标

         y--;

         //不正确的编号

         if(x <  || x >= n || y <  || y >= n)

         {

             ans++;

             continue;

         }

         if(c == )//属于同一类

         {

             if(same(x, y + n) || same(x, y +  * n))ans++;

             else

             {

                 unite(x, y);

                 unite(x + n, y + n);

                 unite(x +  * n, y +  * n);

             }

         }

         else//x吃y

         {

             if(same(x, y) || same(x, y +  * n))ans++;

             else

             {

                 unite(x, y + n);

                 unite(x + n, y +  * n);

                 unite(x +  * n, y);

             }

         }

         //cout<<ans<<endl;

     }

     cout<<ans<<endl;

     return ;

 }

巴特西

POJ-1182 食物链---并查集（附模板）

最新文章

热门文章