【算法每日一练]-图论(保姆级教程篇10 并查集)#POJ1988 #POJ1182
目录
POJ1988
思路:
POJ1182
思路:
POJ1988
有n个栈每个栈中有一个方块,现要执行n次操作。一种是移数,一种是计数
移数M:把包含x的栈整体移动到y栈顶
计数C:统计X方块下面的方块数
输入:
6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4
思路:
我们不需要模拟,我们只需要等价即可,每次操作无非是把一个链表接到了另一个链表上,这完全可以用并查集实现。
设置fa数组表示集合号,cnt表示x号栈中的数量,d为x下方的数量
移数就等价与并查集的合并建树的过程。我们设置祖宗是栈底的方块,然后一边维护fa,cnt,d数组即可。值得注意的是,这三个数组我们都只需要在祖宗那里标记一下就行,然后查找的时候再去更新(类似分块和线段树中懒标思想)。
然后查找祖宗的时候也就是回溯时候既要更新fa(根据祖宗更新),也要更新每个点的d值(根据亲爹更新),(不用更新cnt都一样更新啥呀)
#include <bits/stdc++.h>
using namespace std;
const int N=30005;
int n,fa[N],d[N],cnt[N];//d[x]是x下方的数量,cnt[x]是x号栈中的数量
void init(){
for(int i=1;i<N;i++){
fa[i]=i; d[i]=0; cnt[i]=1;
}
}
//很多时候每个点都要设置d值的,来代表深度
int find(int x)
//我们设置祖先是栈底方块,在查找的时候更新fa和d:fa[x]=find(fa[x]) d[x]=d[x的亲爹]
{
int fx=fa[x];//保存亲爹
if(x!=fa[x]) {//x自己不是祖宗,就要让fa[x]更新成祖宗的集合号
fa[x]=find(fa[x]);
d[x]+=d[fx];//必须让亲爹先是正确的,所以放在dfs之后
}
return fa[x];//返回祖先
}
void unity(int x, int y)//我们要让祖宗能代表整个栈,所以就为祖宗设置cnt
{
int f1=find(x);
int f2=find(y);
fa[f1]=f2;//走到栈底了,进行合并,x栈放在y栈上面
d[f1]=cnt[f2]; //更新x栈祖宗f1的d,因为只需要把根更新正确即可
cnt[f2]+=cnt[f1];//更新y的祖宗f2的cnt
}
int main(){
char ch;
int i,j;
cin>>n;
init();
while(n--){
getchar();//cin,scanf的除了字符型都不怕空格和回车死不掉,但是只管过滤前面的,后面不管
scanf("%c",&ch);
if(ch=='C'){
scanf("%d",&i);
int fi=find(i);//必须先查一边,fi没用的
printf("%d\n",d[i]);
}
else{
scanf("%d%d",&i,&j);
unity(i,j);
}
}
}
POJ1182
有三类动物ABC,A吃B,B吃C,C吃A。现有n只动物(1~n编号),每个动物都是ABC的一种,但是我们并不知道它具体是哪一种。
有两种说法对这n个动物构成的食物链关系进行描述:
第一种说法:1 x y (表示x和y是同类)
第二种说法:2 x y (表示x吃y)
每句话满足以下三条之一就是假话,否则是真话。
1,当前话与前面的某些话冲突,此句话是假话
2,当前话x或y比n大,就是假话
3,当前话x吃x,就是假话 请输出假话的数量
输入:
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
思路:
第2个最好判断。主要是第1,3个话。
并查集的优势是能快速帮你找到关系的祖宗fa和关系的层数d(深度)。而这道题就是利用关系层级解题的。
我们发现直接节点如果构成一条链的话,一定会3种动物进行循环。那么也就是说会形成大量的环。所以如果两种动物本来就在同一个集合的话就不需要合并了。
首先判断吃
如果x和y在同一个集合中且x吃y的话:
(d[x]-d[y]+3)%3=1即可说明是正确的,因为可能有负值所以要多加3。(参考循环队列嘛)
如果不在同一个集合中:
那就fa[x]=y;(d[y]-d[x]+3)%3=1也说明正确。
然后判断同类:
如果x和y在同一个集合中的话:
(d[x]-d[y]+3)%3=0即可说明是正确的,因为可能有负值所以要多加3。
如果不在同一个集合中:
那就fa[x]=y;(d[y]-d[x]+3)%3=0也说明正确。
分析样例:
首先2 1 2,2 2 3 那么构成的并查集为
fa[1]=2 , d[1]=1 查询后变成- >fa[1]=2 , d[1]=2
fa[2]=3 , d[2]=1 fa[2]=3 , d[2]=1
fa[3]=3 , d[3]=0 fa[3]=3 , d[3]=0
然后2 3 3 直接错误。
然后1 1 3 明显不是同类, (d[x]-d[y]+3)%3=2 错误
然后2 3 1 (d[x]-d[y]+3)%3=1 正确
然后1 5 5 (d[x]-d[y]+3)%3=0 正确
然后我们再优化一下:
如果是在不同集合的话,无论是查,还是吃,都需要合并建边不用判断。
但是如果在同一个集合中,无论是吃和是查只需要判断就行。还合并什么呀
那么在同一个集合中,判断公式为:(d[x]-d[y]+3)%3!= c - 1
明显x和y是吃时,c为2时应该和1比较,c为1时应该和0比较。
在不同集合中,合并公式为:fa[a]=b , d[a]=(d[y]-d[x]+3+c - 1)%3
#include <bits/stdc++.h>
using namespace std;
const int N=50010;
int n,fa[N],d[N];
void init(){
for(int i=1;i<=n;i++){
fa[i]=i;
d[i]=0;
}
}
int find(int x){
int fx=fa[x];
if(x!=fa[x]){
fa[x]=find(fa[x]);
d[x]=(d[x]+d[fx])%3;
}
return fa[x];
}
int main(){
int k,c,x,y,tot=0,a,b;
scanf("%d%d",&n,&k);//n个动物,k个描述
init();
while(k--){
scanf("%d%d%d",&c,&x,&y);
if(x>n||y>n||(c==2&&x==y)) tot++;
else {
a=find(x),b=find(y);
if(a==b){
if((d[x]-d[y]+3)%3!=c-1) tot++;
}
else{
fa[a]=b;
d[a]=(d[y]-d[x]+3+c-1)%3;
}
}
}
cout<<tot<<'\n';
}