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