思路:设r(x)表示节点x与根结点的关系,px表示x的根结点。记录每个节点与其父节点的关系,就能很方便知道每个节点以及和它的父节点的关系。
struct node{ int par; //父亲节点 int rel; //与父节点的关系 }a[maxn]; //关系:0表示同类, 1表示父节点吃子节点, 2表示子节点吃父节点
现在给定节点x和y,它们的关系是rel,如何判断这句话是真还是假?
利用find函数找到它们的根结点px和py,以及它们和各自根结点的关系r(x)和r(y),如果px!=py说明x和y没有位于同一集合,那么这句话不会和任何话发生冲突,即这一定是真话,然后合并两个集合;另一种情况就是px==py,说明x和y位于同一集合,现在已经得到x(x)和r(y),那么如何知道x和y的关系呢?我先介绍一下find函数的实现:
int find(int x, int &r) { if(a[x].par == x) { r = x; return a[x].rel; } int y = find(a[x].par, r); a[x].par = r; //路径压缩 return a[x].rel = (a[x].rel + y) % 3; }
find函数每次返回当前节点与根结点的关系,那么在已知当前节点和它的父亲节点关系,父亲节点和根结点的关系,很容易得到当前节点与跟节点的关系r(x) = ( r(a[x].par) + a[x].rel) % 3。
同样对于上面的问题,只需要变换一下x、root、y三者的关系,也能求得x和y的关系r(x, y),如果r(x, y) == rel,说明是真话,否则假话。
注意:所有的关系转换都利用了find函数中的思想,请保证明确关系转换才能看懂unionset函数。
AC代码
#include <cstdio> #include <cmath> #include <cctype> #include <algorithm> #include <cstring> #include <utility> #include <string> #include <iostream> #include <map> #include <set> #include <vector> #include <queue> #include <stack> using namespace std; #pragma comment(linker, "/STACK:1024000000,1024000000") #define eps 1e-10 #define inf 0x3f3f3f3f #define PI pair<int, int> typedef long long LL; const int maxn = 50000 + 5; struct node{ int par; //父亲节点 int rel; //与父节点的关系 }a[maxn]; //关系:0表示同类, 1表示父节点吃子节点, 2表示子节点吃父节点 int find(int x, int &r) { if(a[x].par == x) { r = x; return a[x].rel; } int y = find(a[x].par, r); a[x].par = r; //路径压缩 return a[x].rel = (a[x].rel + y) % 3; } bool unionset(int x, int y, int rel) { int px, py; int rx = find(x, px), ry = find(y, py); if(px != py) { //位于同一集合 ry = (3 - ry) % 3; a[py].par = px; //合并 a[py].rel = (ry + rel + rx) % 3; return true; } else { rx = (3 - rx) % 3; if(rel == (rx + ry) % 3) return true; return false; } } int main() { int n, k; while(scanf("%d%d", &n, &k) == 2) { for(int i = 1; i <= n; ++i) { //初始化并查集 a[i].par = i; a[i].rel = 0; } int d, x, y, ans = 0; for(int i = 0; i < k; ++i) { scanf("%d%d%d", &d, &x, &y); if(x > n || y > n || (d == 2 && x == y)) { ans++; continue; } if(!unionset(x, y, d-1)) ans++; } printf("%d\n", ans); break; //只有一组数据 } return 0; }
如有不当之处欢迎指出!