【带权并查集 —— 是否说谎】Parity game【POJ 1733】

74 阅读 0 评论 49 点赞

我是靠谱客的博主清爽火龙果，最近开发中收集的这篇文章主要介绍【带权并查集 —— 是否说谎】Parity game【POJ 1733】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：

一串由0、1组成的字符串，M次询问，每次询问，小A都会给出一个答案。

每次询问中，有两个数，分别为 l 和 r，然后小A回答在字符串【l,r】这个区间内，有奇数个 1，还是偶数个 1，但是小A会说谎。

问在第 k 组询问中，可以发现小A说谎了，输出最小的 k。

思路：

本题有两种做法，一种是用带权并查集来解决该问题，另一种是用扩展域来解决该问题。

我们先讨论如何用带权并查集来解决该问题。

首先我们可以发现，如果我们要用带权并查集来解决问题，那么对于给出的l和r区间，我们需要用一个值表示这两个点的关系，而这个串又是0、1串，【1,l-1】这个部分他们是公用的，因此我们往前缀和去思考。

想到了前缀和，那么就不难发现，如果【l,r】之间有奇数个1，那么S[l-1]和S[r]的值奇偶互异。

此时我们就可以将 l 节点到 r 节点的边权异或值赋为 1，表示这两点奇偶互异。所以我们可以建立一个数组 d[x] 表示x与其根节点的奇偶情况，若d[x]为0，表示x与其根节点奇偶性相同。d[x]在求取过程中采取求异或和的方法，因为同+同 = 同，异+异 = 同，同+异 = 异，因此异为1，同为0，具体算法如下。

对于每一组询问，先检查 x 和 y 是否在同一个集合中，如果在一个集合中，则 d[x]^d[y] == ans，若不相等，则矛盾。

若不在一个集合中，则合并两个集合，令x = get(a)，y = get(b)，令fa[x] = y，d[x] = d[a]^d[b]^ans，恰好表达了x处与y处的奇偶性差别。

代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define rep(i,a,b) for(int i = a;i <= b;i++)
using namespace std;
const int N = 1e4;

int fa[N],a[N],n,m,tot,d[N];
struct Edge{
	int l,r,id;
}e[N];

int get(int x)
{
	if(fa[x] == x) return x;
	int root = get(fa[x]);
	d[x] ^= d[fa[x]];
	return fa[x] = root;
}

int main()
{
	int T;
	while(~scanf("%d",&T))
	{
		tot = 0;
		scanf("%d",&m);
		rep(i,1,m)
		{
			scanf("%d%d",&e[i].l,&e[i].r);
			e[i].l--;
			char s[10];
			scanf("%s",s);
			a[++tot] = e[i].l, a[++tot] = e[i].r;
			if(s[0] == 'e') e[i].id = 0;
			else e[i].id = 1;
		}
		sort(a+1,a+1+tot);
		tot = unique(a+1,a+1+tot)-a-1;
		rep(i,1,m)
		{
			e[i].l = lower_bound(a+1,a+1+tot,e[i].l)-a;
			e[i].r = lower_bound(a+1,a+1+tot,e[i].r)-a;
		}
		rep(i,1,tot) fa[i] = i;
		rep(i,1,tot) d[i] = 0;
		int jud = 0;
		rep(i,1,m)
		{
			int x = e[i].l, y = e[i].r, ans = e[i].id;
			int fx = get(x), fy = get(y);
			if(fx == fy)
			{
				if(ans != d[x]^d[y]){
					printf("%dn",i-1);
					jud = 1;
					break;
				}
			}
			else{
				fa[fx] = fy;
				d[fx] = d[x]^d[y]^ans;
			}
		}
		if(jud == 0) printf("%dn",m);
	}
	return 0;
}

思路：【拓展域做法】

本题另一种做法就是使用“扩展域”的并查集。

因为每个点只有两种可能，即要么前缀和为奇，要么前缀和为偶数，因此直接拆成两个点进行解决。

当【l,r】之间有偶数个1时，(l-1) 和 r 奇偶性相同，因此fa[l-1] = fa[r]，fa[l-1+n] = fa[r+n]，在赋值之前先判断 (l-1)_odd 和 (r)_even 之前有无分在同一集合中，若有，则矛盾。再令fa[l-1] = fa[r]，fa[l-1+n] = fa[r+n]即可。

当【l,r】之间有奇数个1时，与上种情况做法相似，此处不再赘述。

总结：

当某个点的状态表示为2个或3个等较少个数时，可以考虑使用扩展域来表示各个状态之间的关系来解决问题。

这种方式往往比直接使用带权并查集解决问题要更容易想到，更容易使用。

代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define rep(i,a,b) for(int i = a;i <= b;i++)
using namespace std;
const int N = 1e5;

int fa[N],a[N],n,m,tot;
struct Edge{
	int l,r,id;
}e[N];

int get(int x)
{
	if(fa[x] == x) return x;
	return fa[x] = get(fa[x]);
}

int main()
{
	int T;
	while(~scanf("%d",&T))
	{
		tot = 0;
		scanf("%d",&m);
		rep(i,1,m)
		{
			scanf("%d%d",&e[i].l,&e[i].r);
			e[i].l--;
			char s[10];
			scanf("%s",s);
			a[++tot] = e[i].l, a[++tot] = e[i].r;
			if(s[0] == 'e') e[i].id = 0;
			else e[i].id = 1;
		}
		sort(a+1,a+1+tot);
		tot = unique(a+1,a+1+tot)-a-1;
		rep(i,1,m)
		{
			e[i].l = lower_bound(a+1,a+1+tot,e[i].l)-a;
			e[i].r = lower_bound(a+1,a+1+tot,e[i].r)-a;
		}
		rep(i,1,2*tot) fa[i] = i;
		int jud = 0;
		rep(i,1,m)
		{
			int x = e[i].l, y = e[i].r, ans = e[i].id;
			int fx1 = get(x), fx2 = get(x+tot), fy1 = get(y), fy2 = get(y+tot);
			if(ans == 0)
			{
				if(fx1 == fy2 || fx2 == fy1)
				{
					printf("%dn",i-1);
					jud = 1;
					break;
				}
				fa[fx1] = fy1, fa[fx2] = fy2;
			}
			else{
				if(fx1 == fy1 || fx2 == fy2)
				{
					printf("%dn",i-1);
					jud = 1;
					break;
				}
				fa[fx1] = fy2, fa[fx2] = fy1;	
			}
		}
		if(jud == 0) printf("%dn",m);
	}
	return 0;
}