6.1 优先队列、并查集1

并查集

  1. 实现集合的合并和查找
  2. 用树的形式来储存

优化方式

  1. 按秩合并:将矮的子树接到高的子树上
  2. 路径压缩:将所有父亲、爷爷等根直接与祖先相连
  3. 两种优化只做一个的话的复杂度是nlogn的,但如果两种优化都用的话复杂度是O(1)的;

例题:食物链

题目描述

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

解决方法:

两个动物是同类等价于当动物1是A的时候动物2是A,当动物1是B的时候动物2也是B,动物1为C的时候动物2也是C。动物1吃动物2的时候等价于动物1是A而动物2是B......以此类推。所以需要一个数组来维护这种关系,当i从1到n的时候该动物是A类型,当i从n到2n的时候说明该动物是B类型,当i从2n到3n的时候说明该动物是C类型的

##CODE

#include <bits/stdc++.h>
using namespace std;
const int N = 50000*3 + 5;
int n,k;
int fa[N];
int find(int x)
{
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x,int y)
{
	fa[find(x)] = find(y);
}
int main()
{
	int cnt = 0;
	cin >> n >> k;
	for(int i = 1;i <= n*3;i++) fa[i] = i;
	for(int i = 1;i <= k;i++)
	{
		int op,x,y;
		cin >> op >> x >> y;
		if(x > n || y > n)
		{
			cnt++;
			continue;
		}
		if(op == 1)
		{
			if(find(x) == find(y + n) || find(x) == find(y  + n*2)) cnt++;
			else
			{
				merge(x,y);
				merge(x + n,y + n);
				merge(x + n*2,y + n*2);
			}
		}
		else if(op == 2)
		{
			if(find(x) == find(y) || find(x) == find(y + n*2)) cnt++;
			else
			{
				merge(x,y + n);
				merge(x + n,y + n*2);
				merge(x + n*2,y);
			}
		}
	}
	cout << cnt << "\n";
	return 0;
} 
全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 11:35
程序员小白条:话太多,没实力和学历,差不多回答回答就行了,身份地位不一样
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务