关键词:并查集  图论 相关题目:食物链

题目描述

    动物王国中有三类动物 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 句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。

  • 当前的话与前面的某些真的话冲突,就是假话
  • 当前的话中 X 或 Y 比 N 大,就是假话
  • 当前的话表示 X 吃 X,就是假话

    你的任务是根据给定的 N 和 K 句话,输出假话的总数。

输入输出格式

输入格式:     第一行两个整数,N,K,表示有 N 个动物,K 句话。     第二行开始每行一句话(按照题目要求)

输出格式:

    一行,一个整数,表示假话的总数。

数据规模

AC代码

构造补集法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<cstdio>
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
template <class T>inline void read(T &x){
x=0;
int f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while ('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x*=f;
}
template <class T>inline void read(T &x,T &y,T &z){read(x),read(y),read(z);}

const int N=5e4;
int n,k,n2,f[N*3+5],kkk=0;

int find(int x){
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
int main(){
read(n),read(k);
rep(i,1,n*3) f[i]=i;n2=n*2;
int opt,x,y;
while(k--){
read(opt,x,y);
if(x>n || y>n){++kkk;continue;}
if(opt==1){
if(find(x+n)==find(y) || find(x)==find(y+n)) ++kkk;//相互吃
else{
f[find(x)]=find(y),
f[find(x+n)]=find(y+n),
f[find(x+n2)]=find(y+n2);
}//合并同类
}
else {
if(find(x)==find(y) || find(x+n)==find(y)) ++kkk;//同类 反吃
else{
f[find(x)]=find(y+n),
f[find(x+n)]=find(y+n2),
f[find(x+n2)]=find(y);
}//合并群
}
}
printf("%d\n",kkk);
return 0;
}

带权并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
template <class T>inline void read(T &x){
x=0;
int f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while ('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x*=f;
}
template <class T>inline void read(T &x,T &y,T &z){read(x),read(y),read(z);}
int n,k,kkk=0,f[50005],d[50005];//种类(dis)
int find(int x){
if(f[x]==x) return x;
int fa=f[x];
f[x]=find(f[x]);
d[x]=(d[x]+d[fa])%3;//更新距离
return f[x];
}
int main(){
read(n),read(k);
rep(i,1,n) f[i]=i;
int opt,x,y,a,b;
while(k--){
read(opt,x,y);
if((opt==2&&x==y) || (x>n||y>n)){++kkk;continue;}
a=find(x),b=find(y);
if(opt==1)
if(a==b){
if(d[x]!=d[y]) ++kkk;
}
else {
d[a]=(d[y]-d[x]+3)%3;//调整端点值
//并传递到x节点使d[x]=d[y]
f[a]=b;
}
else
if(a==b){
if(d[x]!=(d[y]+1)%3) ++kkk;
}
else {
d[a]=(d[y]-d[x]+4)%3;//同上
f[a]=b;
}
}
printf("%d\n",kkk);
}