图论洛谷简单习题

并查集

//此处优化为更新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的父亲查找其祖先的次数，但是这个次数恰恰是我们需要的轮数。

#include
using 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 提高组] 关押罪犯
 敌人的敌人是朋友，只要保存当前边的两个人原先有的敌人，再交叉将对方与自己的敌人合在一个并查集即可。这个题很像食物链，就是在扩展空间保存不同关系。
 
#include
using namespace std;
const int N=2e4+7,M=1e5+7;
int n,m;
struct Peo{
    int fa,enemy;
}peo[N];
struct Node{
    int u,v,w;
    bool operator<(const Node &a){return w>a.w;}
}node[M];
int ff(int x){return peo[x].fa==x?x:peo[x].fa=ff(peo[x].fa);}
int join(int x,int y){x=ff(x),y=ff(y);peo[x].fa=y;}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)peo[i].fa=i;
    for(int i=1;i<=m;i++)cin>>node[i].u>>node[i].v>>node[i].w;
    sort(node+1,node+1+m);
    for(int i=1;i<=m;i++){
        int u=node[i].u,v=node[i].v;
        if(ff(u)==ff(v)){
            cout< 
P1197 [JSOI2008]星球大战
 先将所有的连边存储起来，按顺序保存每个要炸毁的点，再连接那些不被炸毁的边，此时的连通块个数就是炸毁
    
     
      
       
        k
       
      
      
       k
      
     
    k个点之后的连通块个数，相当于是最后的连通块个数，因此用栈来存储答案。接下来逆序遍历
    
     
      
       
        k
       
      
      
       k
      
     
    k个要炸毁的点，每次添加一个点及其连边。每次连边都是将两个连通块变成一个，因此连通块总个数减少1。
 
#include
using namespace std;
const int N=4e5+7,M=2e5+7;
vectorson[N];
int fa[N],n,m,k,broken[N],stk[N],top;
bool vis[N];
int ff(int x){return fa[x]==x?x:fa[x]=ff(fa[x]);}
int main(){
    cin>>n>>m;
    for(int i=0;i>u>>v;
        son[u].push_back(v);son[v].push_back(u);
    }
    cin>>k;
    int cnt=n-k;

    for(int i=1;i<=k;i++){
        cin>>broken[i];
        vis[broken[i]]=true;
    }
    for(int u=0;u