动物王国中有三类动物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和K句话,输出假话的总数。
输入格式
第一行是两个整数N和K,以一个空格分隔。
以下K行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中D表示说法的种类。
若D=1,则表示X和Y是同类。
若D=2,则表示X吃Y。
输出格式
只有一个整数,表示假话的数目。
样例:
输入样例: 100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5 输出样例: 3
首先讲一下这个题目的意思,A 吃 B,B 吃 C,C 吃 A。
如果按被吃的方向来画,那么C->B->A A->C,这样就形成了一个闭环,也正是生物圈能量的循环
我们这题采用并查集的思想
食物链绕不开 A->C B->A C->B 因此,利用边的权重,即当前点到根节点的距离作为约束条件 假设根为a(也可以是b,c,因为这是闭环) 有以下三种情况: 1. a和b b->a b到根节点a的距离为1,表示b能被a吃 2. a和c c->b->a c到根节点a的距离为2,表示c能吃a,且c被b吃 3. a和a a->c->b->a a到根节点a的距离为3, 表示a和a是同类
所以我们创建两个集合,一个存放动物,另外一个存放其到父节点的距离
我们将距离对3取余,如果结果为1,则是第一种情况,为2则是第二种情况,为0则是第三种情况
private static int find(int x) {;
if(p[x]!=x){
int tmp=find(p[x]); //开始递归;最终用tmp储存根节点
d[x]+=d[p[x]]; //递归结束后为该点到根节点的距离
p[x]=tmp; //将每个点的父节点设为根节点
}
return p[x]; //返回父节点
}
import java.io.*;
public class Main {
static int N=50010;
static int []p=new int[N]; //存放动物
static int []d=new int[N]; //存放每个节点到父节点的距离
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String []s=br.readLine().split(" ");
int n=Integer.parseInt(s[0]),k=Integer.parseInt(s[1]);
for (int i = 1; i <=n; i++) { //初始化动物堆
p[i]=i;
}
int res=0; //最后结果
while (k-->0){
String []fir=br.readLine().split(" ");
int D=Integer.parseInt(fir[0]);
int x=Integer.parseInt(fir[1]);
int y=Integer.parseInt(fir[2]);
if(x>n || y>n){
res++;
}else {
//px,py分别储存根节点
int px=find(x); int py=find(y);
if(D==1){
//如果x和y在同一个集合中,但是距离差不为0则说明不是同类是假话
if(px==py && (d[x]-d[y])%3!=0) {
res++;
} else if(px!=py){
//如果不在同一个集合则让x的根节点的父节点变为y的根节点
p[px]=py;
//(d[x]+d[px]-d[y])%3==0
d[px]=d[y]-d[x];
}
}else {
//如果x和y在同一个集合中,但是距离差不为1则说明不是被吃的关系是假话
if(px==py && (d[x]-1-d[y])%3!=0){
res++;
}else if(px!=py){
p[px]=py;
//(d[x]+d[px]-d[y]-1)%3==0
d[px]=d[y]+1-d[x];
}
}
}
}
System.out.println(res);
}
private static int find(int x) {;
if(p[x]!=x){
int tmp=find(p[x]); //开始递归;最终用tmp储存根节点
d[x]+=d[p[x]]; //递归结束后为该点到根节点的距离
p[x]=tmp; //将每个点的父节点设为根节点
}
return p[x]; //返回父节点
}
}