poj1182 种类并查集

本文主要是介绍poj1182 种类并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

有点坑的题目，不过做做绝对利大于弊，尤其在你不断WA到哭的时候，大神忽略这句

0：两者相同级别

1：被根节点吃

2：吃根节点

原因：对于输入的关系1和2，减1之后便是输入的两个量之间的关系（其实是写完题目之后看解题报告发现这规律的）

#include <iostream>
#include <cstring>using namespace std;int father[50005];
int rank[50005];
int n,m;void init()
{memset(rank,0,sizeof(rank));for (int i=0; i<50005; i++)         //因为写成<=50005，WA了一下午都找不到原因，WA哭了都才发现这个细节。。。 father[i] = i;
}int find(int x)                         //路径压缩 
{if (x == father[x])return x;int t = father[x];father[x] = find(father[x]);rank[x] = (rank[x] + rank[t])%3;return father[x];
}int Union(int a,int b,int d)
{int x = find(a);int y = find(b);if (x == y){if ((rank[a]+d-1)%3 == rank[b])         //找规律，很容易发现，毕竟只有六种情况 return 1;elsereturn 0;}else{father[y] = x;rank[y] = (rank[a]-rank[b]+d+2)%3;      //y与x的关系可通过x->a->b->y确定，rank[y]=a与x的关系+b与a的关系+y与b的关系=rank[a]+(d-1)+3-rank[b]//原因与find函数中rank更新方法相同，find函数中的更新方法可推理获得 }return 1;
}int main()
{scanf("%d%d",&n,&m);init();int sum=0;while (m--){int a,b,s;scanf("%d%d%d",&s,&a,&b);if (a>n||b>n)                           //注意这也是不满足题意的情况 sum++;else if (!Union(a,b,s))                 //注意要else sum++;}cout<<sum<<endl;return 0;
}

这篇关于poj1182 种类并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---