「Codeforces 1131F」Asya and Kittens

发表于 | | 阅读次数:
字数统计: 549 字

Description

题目链接：Codeforces 1131F

Asya 最近买了 $n$ 只小猫，把它们标号为 $1$ 到 $n$ 并放在笼子里。笼子由一行 $n$ 个格子组成，从左到右标号为 $1$ 到 $n$。相邻的格子之间透明的隔板，所以起初有 $n-1$ 个隔板。最初每个格子里只有一个只小猫。

经过观察，Asya 注意到相邻格子中的小猫想要一起玩。因此 Asya 开始删除相邻格子隔板。具体来说，在第 $i$ 天：

  • 注意到相邻的小猫 $x_i$ 和 $y_i$ 想到一起玩。
  • 将这两个格子之间的隔板移除，创建了一个新的格子，原来两个格子里的小猫都到这个新的格子里。

Asya 不会把隔板重新放回去，因此 $n-1$ 天后笼子里只有一个格子，所有的小猫都在里面。

每一天，Asya 都记得有哪一对小猫 $x_i,y_i$ 想到一起玩，但是她不记得一开始是怎么把小猫放到笼子里的。请帮助她找到小猫在 $n$ 个格子里的可能初始排列。数据保证有解，输出任意一个合法解即可。

数据范围：$2\le n\le 1.5\times 10^5$

Solution

对于新建一个格子，我们将其看做是新建了一个点，这个点的左右儿子为原来的两个点（这两个点可能不是叶子，可能是之前合并得到的）。

这样我们得到了一棵二叉树。我们令最后一个点为根进行前序遍历，叶子节点在这个遍历中的序列就是答案。

时间复杂度：$O(n\cdot\alpha(n))$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
#include <cstdio>
#include <algorithm>

const int N=3e5+5;
int n,fa[N],ls[N],rs[N];

int find(int x) {
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void dfs(int x) {
    if(x<=n) printf("%d ",x);
    else dfs(ls[x]),dfs(rs[x]);
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n+n;++i) fa[i]=i;
    int m=n;
    for(int i=1;i<n;++i) {
        int x,y;
        scanf("%d%d",&x,&y);
        x=find(x),y=find(y);
        ls[++m]=x,rs[m]=y;
        fa[x]=fa[y]=m;
    }
    dfs(m);
    puts("");
    return 0;
}
0%