BNU 51275 道路修建 Large 并查集

分析（引入Q神题解 %%%Q）

如果使用可持久化并查集，二分答案判定连通性，复杂度是O(mlog3n)，不能在时限内出解。
考虑到并查集实际上是一棵树，可以尝试在边上维护一些信息，假设t时刻加了一条边(u,v)，若u和v此时未连通，
则在root(u)和root(v)之间连一条权值为t的边，表示u所在集合以及v所在集合在t时刻连通，
这样对于一组查询(u,v)，如果u和v位于同一个连通块内，只需找出并查集中u到v的路径上的权值最大值，
很显然这样是不能路径压缩的，但是可以按秩合并保证树高是O(logn)，总的复杂度是O(mlogn)。

这样找到树根是logn,路径查询也是logn 总的是mlogn,关键是代码很好写

#include<cstdio>

#include<algorithm>

#include<iostream>

using namespace std;

typedef long long LL;

const int N=1e5+;

int fa[N],r[N],p[N],vis[N],n;

void init()

{

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

   {

      fa[i]=i;

      p[i]=r[i]=;

      vis[i]=-;

   }

}

int find(int x)

{

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

    return find(fa[x]);

}

bool Union(int u,int v,int t)

{

    u=find(u);

    v=find(v);

    if(u==v)return false;

    if(r[u]>r[v])

    {

       fa[v]=u;

       p[v]=t;

    }

    else

    {

       fa[u]=v;

       p[u]=t;

       if(r[u]==r[v])++r[v];

    }

    return true;

}

int getans(int u,int v)

{

    int now=,x=u,ans;

    while()

    {

       vis[x]=now;

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

       now=max(now,p[x]);

       x=fa[x];

    }

    x=v,now=;

    while()

    {

       if(vis[x]!=-)

       {

           now=max(now,vis[x]);

           ans=now;

           break;

       }

       now=max(now,p[x]);

       x=fa[x];

    }

    x=u;

    while()

    {

       vis[x]=-;

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

       x=fa[x];

    }

    return ans;

}

int main()

{

    int T,la,m;

    scanf("%d",&T);

    while(T--)

    {

       scanf("%d%d",&n,&m);

       init(),la=;

       int op,u,v,blk=n;

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

       {

          scanf("%d%d%d",&op,&u,&v);

          u^=la,v^=la;

          if(op)

          {

              int x=find(u);

              int y=find(v);

              if(x!=y)

                  la=;

              else la=getans(u,v);

              printf("%d\n",la);

          }

          else

          {

              if(Union(u,v,i))blk--;

              la=blk;

              printf("%d\n",la);

          }

       }

    }

    return ;

}

巴特西

BNU 51275 道路修建 Large 并查集

最新文章

热门文章