【并查集】POJ1182食物链 - 木东驿站 - Powered by MoodBlog

CONTENT

【并查集】POJ1182食物链

题目描述

动物王国中有三类动物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),输出假话的总数。 

输入

第一行是两个整数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

个人感受

去年接触了并查集,并没有做多少训练,这次竟然连合并都写错了……还是得仔细啊。

一定要记住并查集合并是根节点合并哦0.0

JAVA代码

import java.util.Scanner;
public class Main{
	public static void main(String args[]){
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int K = scanner.nextInt();
		int ans = 0;
		BFsets bf = new BFsets(3*N);
		for(int i=0;i<K;i++){
			int t = scanner.nextInt();
			int x = scanner.nextInt()-1;
			int y = scanner.nextInt()-1;
			if(x<0||x>=N||y<0||y>=N){
				ans++;
				continue;
			}
			if(t==1){

				if(bf.issame(x,y+N)||bf.issame(x+N,y)){
					ans++;
				}else{
					bf.unionSets(x,y);
					bf.unionSets(x+N, y+N);
					bf.unionSets(x+2*N, y+2*N);
				}
			}else{
				if(bf.issame(x, y)||bf.issame(x, y+2*N)){
					ans++;
				}else{
					bf.unionSets(x, y+N);
					bf.unionSets(x+N, y+2*N);
					bf.unionSets(y, x+2*N);
				}
			}
		}
		System.out.println(ans);
	}
}
class BFsets{
	public int[] data;
	public BFsets(int n){
		data = new int[n];
		for(int i=0;i<n;i++){
			data[i] = i;
		}
	}
	public int getParent(int n){
		if(data[n]==n){
			return n;
		}else{
			data[n] =  getParent(data[n]);
			return data[n];
		}
	}
	public boolean issame(int a,int b){
		return getParent(a)==getParent(b);
	}
	public void unionSets(int a,int b){
		int x = getParent(a);
		int y = getParent(b);
		data[x] = y;
	}
}


个快快 2018年03月07日 天气 晴

REMARKS

© 2018 MoodBlog 0.2 个快快 作品 | 参考主题: mathilda by fuzzz. | 鲁ICP备16047814号