首页 > 其他分享 >POJ1182 食物链 (并查集的应用)

POJ1182 食物链 (并查集的应用)

时间:2024-01-30 15:23:34浏览次数:29  
标签:食物链 POJ1182 查集 ++ 节点 int ans else find

POJ1182 食物链 (并查集的应用)

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

题解:利用r[]来记录子节点与父节点的关系,0表示同类,1表示吃,2表示被吃,每次find之后,压缩路径,把子节点的父节点都变为根节点。

#include <cstdio>
#include <cstring>
#define maxn 50005
int f[maxn];//父节点 
int r[maxn];//子节点与父节点的关系 
void init(){
	for(int i = 0;i < maxn;i++){
		f[i] = i;
		r[i] = 0;
	}
}
int find(int x){
	if(x != f[x]){
		int tp = f[x];
		f[x] = find(f[x]);
		r[x] = (r[x] + r[tp]) % 3;
	}
	return f[x];
}
void Union(int x, int y, int re){
	int xx = find(x), yy = find(y);
	f[xx] = yy;
	r[xx] = (3 - r[x] + re + r[y]) % 3;
}
int main() {
	int n,m,d,x,y;
	scanf("%d%d", &n,&m);
	int ans = 0;
	init();
	while(m--){
		scanf("%d%d%d", &d, &x, &y);
		if(x > n || y > n) ans++;
		else if(d == 1){
			if(find(x) == find(y) && r[x] != r[y]) ans++;
			else Union(x,y,0);
		}
		else {
			if(x == y) ans++;
			else {
				if(find(x) == find(y) && (3 - r[y] + r[x]) % 3 != 1) ans++;
				else {
					Union(x,y,1);
				}
			}
		}
		//printf("%d\n",ans);
	} 
	printf("%d\n",ans);
	return 0;
}

标签:食物链,POJ1182,查集,++,节点,int,ans,else,find
From: https://www.cnblogs.com/zhclovemyh/p/17997186

相关文章

  • POJ2492 (并查集)
    POJ2492(并查集)题目:假设昆虫之间是异性互动,给出昆虫的互动情况,判断假设是否成立;输入:第一行t表示n个测试用例,每个测试用例第一行n,m表示n只昆虫,从1连续编号,m组互动情况;输出:假设不成立:Suspiciousbugsfound!假设成立:Nosuspiciousbugsfound!题解:参考POJ1611#include<cstdio......
  • POJ1611 (简单并查集)
    POJ1611(简单并查集)描述严重急性呼吸系统综合症(SARS)是一种病因不明的非典型肺炎,于2003年3月中旬被确认为全球性威胁。为了尽量减少传染给他人,最好的策略是将嫌疑人与其他人分开。在不传播你的疾病大学(NSYSU),有很多学生团体。同一小组中的学生相互交流频繁,一个学生可能会......
  • POJ 2524 (简单并查集)
    POJ2524(简单并查集)描述当今世界上有如此多不同的宗教,很难将它们全部记录下来。您有兴趣了解您所在大学的学生信仰多少种不同的宗教。您知道您的大学有n名学生(0<n<=50000)。你不可能询问每个学生的宗教信仰。此外,许多学生不愿意表达自己的信仰。避免这些问题的一种方......
  • 并查集
    简介并查集是一种维护集合的数据结构。支持合并和查询元素所在集合。我们将所有元素用点表示,从属关系用边表示,那么每个集合构成了一棵有向树。每个点有且仅有一条出边,指向其父亲。其中根节点的出边指向自己。集合用根节点的编号代表。实现初始化一开始所有的元素指向自己。......
  • 【模板】并查集
    并查集是解决两元素是否属于同一集合,将一个集合合并另一集合的数据结构。具体来说,我们使用数字代替集合,比如集合1,集合2.使用数组f[i]维护元素i属于的集合,比如f[2]=4表示元素2属于集合4。具体我们有以下实现功能的代码1初始化表示集合的数组。cin>>n>>m;for(int......
  • Codeforces Round 170 (Div. 1)A. Learning Languages并查集
    如果两个人会的语言中有共同语言那么他们之间就可以交流,并且如果a和b可以交流,b和c可以交流,那么a和c也可以交流,具有传递性,就容易联想到并查集,我们将人和语言看成元素,一个人会几种语言的话,就将这些语言和这个人所在的集合合并,最后求一下人一共在几个连通块中,连通块的个数-1就是答案,......
  • P1536 村村通(并查集)
    村村通题目描述某市调查城镇交通状况,得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府"村村通工程"的目标是使全市任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要相互之间可达即可)。请你计算出最少还需要建设多少条道路?输入格式输入包含若干......
  • CF-1184-E3-最小生成树+倍增+并查集
    1184-E3题目大意给定一个\(n\)个点,\(m\)条边的无向图,边带权。对于每条边,你需要找到最大值\(x\),使得把这条边的权值修改为\(x\)后能够出现在最小生成树上。Solution先把整个图的最小生成树弄出来,然后将边分为树边以及非树边来考虑:非树边:对于一个非树边连接了\(x\)和\(y\)的......
  • 并查集与反集——P1892团伙
    并查集并查集如其名,合并与查找查找intfind(intkey){ if(fa[key]==key)returnkey; elsereturnfa[key]=find(fa[key]);}合并voidunite(intx,inty){ intfax=find(x); intfay=find(y); fa[fax]=fay; return;}反集处理并查集合并问题的敌对/......
  • 并查集
    并查集是一种集合结构,用来处理集合的合并和查询问题。主要有两个函数:合并和查询合并函数表示合并两个不同的集合查询表示当前元素属于那个集合逻辑结构是单链表的结构,每个节点向上指向一个属于的集合的代表元素,这个集合的代表元素的next指向它自己成环,表示这个集合的代表元素......