Codeforces 541 F. Asya And Kittens（并查集+DFS）

本文主要是介绍Codeforces 541 F. Asya And Kittens（并查集+DFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意是说，输入 $n$ ，表示有 $n$ 个数 $1$ ~ $n$ ，接下来有 $n - 1$ 对关系，每行输入两个数 $a$ 和 $b$ ，表示将 $a$ 所在的集合与 $b$ 所在的集合合并，但是合并有前提条件， $a$ 所在的集合与 $b$ 所在的集合必须相邻（数组的第一个和最后一个不算相邻）。求这组序列最开始的排列情况，答案不唯一，输出一组答案即可

做这道题前必须会：并查集、DFS

并查集很容易想到，因为涉及到多个集合的相关操作，主要是如何模拟两个集合之间的相对位置

创建一个二维邻接表List<Integer>[] t， $t [i]$ 中存放的是以 $i$ 为根节点，所有与 $i$ 处于同一集合的元素，因此如果合并 $a$ 和 $b$ ，还需要将 $b$ 所在集合的根节点 $f b$ 添加到 $a$ 所在集合的根节点 $f a$ 的邻接表中，然后将 $f b$ 的根节点更新为 $f a$ 。具体操作就是

fa = find(a);
fb = find(b);
t[fa].add(fb);
father[fb] = fa;

合并完了以后就要进行DFS遍历，将二维邻接表中的元素打印出来即是答案，对于样例来说，合并完以后，二维邻接表的状态如下图左边，集合（没有使用路径压缩）状态如下图右边

DFS遍历的时候进入的节点可以是任意节点的根节点，但是由于 $\geq 2$ ，所以最好不要寻找 $x (x > 3)$ 的根节点作为起点，因为可能 $x$ 就根本不存在。我以1节点的根节点作为起点进行遍历，也就是dfs(find(1))，那么对于上面的图来说，输出的答案应就是31425

import java.io.BufferedInputStream;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Scanner;public class Main {static int[] father;static ArrayList<Integer>[] t;static BufferedWriter print = new BufferedWriter(new OutputStreamWriter(System.out));static int find(int x) {if (father[x] == x)return x;return father[x] = find(father[x]);}static void union(int a, int b) {a = find(a);b = find(b);if (a != b) {t[a].add(b);father[b] = a;}}public static void main(String[] args) throws IOException {Scanner cin = new Scanner(new BufferedInputStream(System.in));int n = cin.nextInt();father = new int[n + 1];t = new ArrayList[n + 1];for (int i = 1; i <= n; i++) {father[i] = i;t[i] = new ArrayList<Integer>();}for (int i = 0; i < n - 1; i++) {int p = cin.nextInt();int q = cin.nextInt();union(p, q);}dfs(find(3));print.flush();}static void dfs(int root) throws IOException {print.write(root + " ");for (int i = 0; i < t[root].size(); i++)dfs(t[root].get(i));}
}