图论洛谷简单习题

并查集 并查集

//此处优化为更新x的祖先时顺便更新了x父亲的祖先也为x的祖先int ff(x){return fa[x]==x?x:fa[x]=ff(fa[x]);}int join(int x,int y){x=ff(x),y=ff(y);x=fa[y];}

P2661 [NOIP2015 提高组] 信息传递
用并查集难的地方是在寻找父亲和合并过程的变化。要了解合并和寻找过程对题目变量的影响。
一旦 i i i查询的 x x x和 i i i不是直接父子关系，继续向上查找合并就应该算成另外一轮，并且是当前轮之前的轮数确定的并集关系。
同时模板中查找父亲时顺便更新父亲的祖先的优化也不能加入，因为这个优化的作用在于将 x x x并查集内的所有节点都变成 x x x祖先的直接后继，将整个并集变成二层结构，从而减少 x x x的父亲查找其祖先的次数，但是这个次数恰恰是我们需要的轮数。

#includeusing namespace std;const int N=200007;int fa[N],n,ans=0x3f3f3f3f,cnt;int ff(int x){ cnt++; return fa[x]==x?x:ff(fa[x]);}int main(){ cin>>n; for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=n;i++){ cnt=0; int x;cin>>x; if(ff(x)!=i){ fa[i]=x; } else ans=min(cnt,ans); } cout<

P1525 [NOIP2010 提高组] 关押罪犯
敌人的敌人是朋友，只要保存当前边的两个人原先有的敌人，再交叉将对方与自己的敌人合在一个并查集即可。这个题很像食物链，就是在扩展空间保存不同关系。