两个两个输入我是卡一些数D代表这两个数不同,A代表查询这两个数是否相同
与食物链那一题类似都是开多倍数组,储存每种情况
两个两个输入我是卡一些数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万+