Asya And Kittens – CF131-F – 并查集

题目连接

https://codeforces.com/contest/1131/problem/F

题目大意

一组笼子里关着猫,每一个笼子里的猫都有一个自己的编号。猫可以打破笼子之间的隔板当且仅当它要找的那只猫与它之间只有一个隔板,按时间顺序给出一系列猫与它想要找的猫,问笼子中的猫如何排列才能让最终所有的猫都在一个笼子里。

解题思路

用并查集维护当前块的左端点,右端点与每一个元素的下一个元素
下面是并查集合并部分的代码

void zhan(int x,int y)
{
    int a=findroot(x),b=findroot(y);
    fa[b]=a;
    nxt[r[a]]=l[b];
    last[l[b]]=r[a];
    r[a]=r[b];
}

其中fa是根节点,nxt是它的下一个元素,last是它的上一个元素,r是左端点,l是右端点。
因为是让a作为b的根节点,所以让a在左b在右的话,那么a的右端点的下一个就是b的左端点,b的左端点的左面就是a的右端点。合并后b被合并到a中,所以a的右端点要更新为b的右端点。
输出时通过nxt数组一个一个输出即可
代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

const int maxn=200020;

int fa[maxn],nxt[maxn],last[maxn],l[maxn],r[maxn];

void init(int n)
{
    for(int i=0; i<=n; i++)
    {
        fa[i]=i;
        nxt[i]=-1;
        last[i]=-1;
        l[i]=i;
        r[i]=i;
    }
}

int findroot(int x)
{
    return fa[x]=fa[x]==x?x:findroot(fa[x]);
}

void zhan(int x,int y)
{
    int a=findroot(x),b=findroot(y);
    fa[b]=a;
    nxt[r[a]]=l[b];
    last[l[b]]=r[a];
    r[a]=r[b];
}

int main()
{
    int n;
    cin>>n;
    init(n);
    int x,y;
    for(int i=1; i<n; i++)
    {
        cin>>x>>y;
        zhan(x,y);
    }
    int s;
    for(int i=1;i<=n;i++)
    {
        if(last[i]==-1)
        {
            s=i;
            break;
        }
    }
    for(int i=s;i!=-1;i=nxt[i])
    {
        cout<<i<<" ";
    }
    return 0;
}

发表评论

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