POJ - 1703 Find(为什么我老是断输入我是卡啊。。。)

两个两个输入我是卡一些数D代表这两个数不同,A代表查询这两个数是否相同

与食物链那一题类似都是开多倍数组,储存每种情况


  

  

题目大意:A操作是询问x和y的关系(3种之一)D操作说明x和y不在一个帮

思路:并查集,但是和普通并查集不一样两种方法:①开两倍的空间,两个并查集②用向量偏移寫。

 
方法②:向量偏移方法该方法不是太熟悉,只是自己梳理一下

之所以叫向量偏移,肯定是和向量有关系
先从find函数说起,find函数在找父亲节点的同时更新了整体的关系。这个公式是可以由假设关系推出来的
设a与b的关系为r1,b与c的关系是r2那么a与c的关系就是(r1+r2)%2;
列表,枚舉所有关系可以看出来这个规律。(具体参考上面博客)
再说Union函数 把fx合并到fy,那么fx 对 fy的关系 见下图
x对y的关系为1(同类为0),不同类財合并
 //不知道和食物链的有什么区别这里可以用rank数组 
 

A a b表示询问成员a和b的帮派关系

D a b表示a囷b在不同的帮派中

发布了2 篇原创文章 · 获赞 0 · 访问量 2万+

我要回帖

更多关于 输入我是卡 的文章

 

随机推荐