洛谷 P2661信息传递

图论——>并查集 P2661

本蒟蒻啥也不会 这题还WA了1次 =  = 最后看题解A 哭了

看题是多个（N<=200000）东西之间的关系维护 果断想到并查集

在第i个位置的a[i] 表示i告诉a[i]

那么从i向a[i]连边 同时要维护点和点之间的距离(注意顺序 不要瞎连=  =)

代码表示就是

int a=find(i) ,b=find(a[i]);

fa[a]=b,dis[i]=dis[a[i]]+1;

关于find怎么写？

int find (int a){

if(a==fa[a]) return fa[a];

int root =fa[a];

fa[a]=find [fa[a]];//之所要先find是为了保证root的dis值正确

dis[a]+=dis[root];

return fa[a];     }

关键就是这样了 剩下的自己理一理想想思路吧

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#define N 200010

using namespace std;

int n;

int fa[N],dis[N];

int find(int x)

{

    if(fa[x]==x) return x;

    else {

        int last=fa[x];//make dis[fa[x]] right

        fa[x]=find(fa[x]);

        dis[x]+=dis[last];

        return fa[x];

    }

}

int main()

{

    //reopen("testdata(5).in","r",stdin);

    int ans=0x7fffffff;

    cin>>n;

    for(int i=;i<=n;i++)

        fa[i]=i;

    for(int i=;i<=n;i++)

    {

        int tra1;

        scanf("%d",&tra1);

        int fa1=find(i),fa2=find(tra1);

        if(fa1==fa2)//ring found

        {

            ans=min(ans,dis[tra1]+dis[i]+);

        }

        else {

            fa[fa1]=fa2;

            dis[i]=dis[tra1]+;

        }

    }

    cout<<ans;

    return ;

}

嗯哼~

TAG:SIN_XIII ⑨