Connecting Graph Gym – 100814C – LCA

题目链接

https://cn.vjudge.net/problem/Gym-100814C

题目大意

代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+50;
int n,m,tot;

int fa[maxn],dis[maxn];
int up[maxn][25],maxx[maxn][25];
vector<pair<int,int> >edge[maxn];

struct node
{
    int p,u,v;
}q[maxn];

void init()
{
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
    }
    memset(dis,0,sizeof(dis));
    memset(up,0,sizeof(up));
    memset(maxx,0,sizeof(maxx));
    memset(edge,0,sizeof(edge));
    tot=0;
}

int findd(int x)
{
    if(fa[x]==x)
        return x;
    else return fa[x]=findd(fa[x]);
}

void dfs(int u)
{
    for(int i=0;i<edge[u].size();i++)
    {
        int v=edge[u][i].first;
        int len=edge[u][i].second;
        if(dis[v]==0)
        {
            dis[v]=dis[u]+1;
            maxx[v][0]=len;
            up[v][0]=u;
            dfs(v);
        }
    }
}

void init_lca()
{
    for(int j=1;(1<<j)<=n;j++)
    {
        for(int i=1;i<=n;i++)
        {
            up[i][j]=up[up[i][j-1]][j-1];
            maxx[i][j]=max(maxx[i][j-1],maxx[up[i][j-1]][j-1]);
        }
    }
}

int getans(int a,int b)
{
    if(dis[a]<dis[b])
        swap(a,b);
    int c=dis[a]-dis[b],res=0;
    for(int i=0;(1<<i)<=n;i++)
    {
        if(c&(1<<i))
        {
            res=max(res,maxx[a][i]);
            a=up[a][i];
        }
    }
    if(a==b)
    {

        return res;
    }
    for(int i=20;i>=0;i--)
    {
        if(up[a][i]!=up[b][i])
        {
            res=max(res,maxx[a][i]);
            res=max(res,maxx[b][i]);
            a=up[a][i];
            b=up[b][i];
        }
    }
    return max(res,max(maxx[a][0],maxx[b][0]));
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        init();
        for(int i=1;i<=m;i++)
        {
            int x,u,v;
            cin>>x>>u>>v;
            if(x==1)
            {
                int fu=findd(u),fv=findd(v);
                if(fu==fv)
                {
                    continue;
                }
                fa[fu]=fv;
                edge[u].push_back(make_pair(v,i));
                edge[v].push_back(make_pair(u,i));
            }
            else
            {
                q[++tot].p=i;
                q[tot].u=u;
                q[tot].v=v;
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(dis[i]==0)
            {
                dis[i]=1;
                dfs(i);
            }
        }
        init_lca();
        for(int i=1;i<=tot;i++)
        {
            int fu=findd(q[i].u),fv=findd(q[i].v);
            if(fu!=fv)cout<<"-1"<<endl;
            else
            {
                int ans=getans(q[i].u,q[i].v);
                if(ans>q[i].p)cout<<"-1"<<endl;
                else cout<<ans<<endl;
            }
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注