Description
动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B, B吃C,C吃A。
现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述:
第一种说法是"1 X Y",表示X和Y是同类。
第二种说法是"2 X Y",表示X吃Y。
此人对N个动物,用上述两种说法,一句接一句地说出K句话,这K句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。
1) 当前的话与前面的某些真的话冲突,就是假话;
2) 当前的话中X或Y比N大,就是假话;
3) 当前的话表示X吃X,就是假话。
你的任务是根据给定的N(1 <= N <= 50,000)和K句话(0 <= K <= 100,000),输出假话的总数。Input
第一行是两个整数N和K,以一个空格分隔。
以下K行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中D表示说法的种类。
若D=1,则表示X和Y是同类。
若D=2,则表示X吃Y。Output
只有一个整数,表示假话的数目。
Sample Input
100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5
Sample Output
3
首先要意识到本题是路径压缩并查集问题。对于任意节点X与Y,只要X与Y在同一个分量中,就表示他们之间的关系是已知的(可以通过中间节点推出来)。
设节点A->节点B的值=节点A与节点B的关系:
A->B==0 表示A与B同类,此时B->A也==0(B与A同类)。
A->B==1表示A吃B,此时B->A==2(B被A吃)。
A->B==2表示A被B吃,此时B->A==1(B吃A)。
通过任意A->B和B->C的关系,我们能推出A->C的关系。通过任意A与B关系,B与C关系,C与D关系我们能推出A与D关系。因为A->B的值等于B->A的值的逆(想想是不是)。
分析到此我们可以用一般的路基压缩并查集来做本题,即:
findset(x)时,先找出x的父亲节点->根的关系v2,然后用r[x](表x到x父亲的关系)与v2合并可以得出x到根的关系。比如x->父==1时,父->根==1时,那么x->根==2(想想是不是)。
对于bind(u,v,relation)来说,只要找出u->u分量根的关系,v->v分量根的关系,且利用u与v的关系relation,可以推断出u分量根fu与v分量根fv的关系。
对于并查集的基础结构就做完了,当如果输入r x y时,且x与y在同一分量(x与y的关系可推断出),那么只要x与y的关系与r所指关系不同,那么说明本句是假话。另外两种假话情况很简单就不讨论了。
AC代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include<queue>
#include<map>
#include<vector>
#include<math.h>
const int INF = 0x3f3f3f3f;
using namespace std;
typedef long long ll;
typedef double ld;
typedef unsigned long long ull;
const int maxn=50000+5;
int fa[maxn];
int r[maxn];//与父的关系
int rev(int val)//返回逆向关系
{
return (3-val)%3;
}
int rela_2(int v1,int v2)//由两个连续关系推出1个直接关系
{
if(v1==0) return v2;
if(v2==0) return v1;
if(v1==1 && v2==1) return 2;
if(v1==1 && v2==2) return 0;
if(v1==2 && v2==1) return 0;
if(v1==2 && v2==2) return 1;
}
int rela_3(int v1,int v2,int v3)//3间接关系推1直接关系
{
return rela_2(rela_2(v1,v2),v3);
}
int findset(int x)
{
if(fa[x]==-1) return x;
int root=findset(fa[x]);
r[x] = rela_2(r[x],r[fa[x]]);
return fa[x]=root;
}
int bind(int u,int v,int relation)
{
int fu=findset(u);
int fv=findset(v);
if(fu!=fv)
{
r[fu]=rela_3(rev(r[u]), relation, r[v]);
fa[fu]=fv;
return 0;
}
else//u与v在同一连通分量
{
if(rela_2(r[u], rev( r[v] ) ) != relation) return 1;
return 0;
}
}
int main()
{
int n,k;
int cnt=0;//假话数
scanf("%d%d",&n,&k);
memset(fa,-1,sizeof(fa));
memset(r,0,sizeof(r));
while(k--)
{
int relation,x,y;
scanf("%d%d%d",&relation,&x,&y);
relation--;//这里记得减1
if(x>n || y>n || (relation==2 && x==y) )
{
++cnt;
continue;
}
cnt += bind(x,y,relation);
}
printf("%d\n",cnt);
return 0;
}
标签:关系,return,int,查集,1182,v2,POJ,relation,include From: https://blog.51cto.com/u_15952369/6035578