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$ 所在集合的根节点 $fb$ 添加到 $a$ 所在集合的根节点 $fa$ 的邻接表中，然后将 $fb$ 的根节点更新为 $fa$。具体操作就是

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

合并完了以后就要进行 DFS 遍历，将二维邻接表中的元素打印出来即是答案，对于样例来说，合并完以后，二维邻接表的状态如下图左边，集合（没有使用路径压缩）状态如下图右边
DFS 遍历的时候进入的节点可以是任意节点的根节点，但是由于 $n \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));
    }
}

使用了一个输入输出优化，避免 TLE