MENU

Codeforces 541 F. Asya And Kittens(并查集+DFS)

February 24, 2019 • Read: 247 • 算法


题目大意是说,输入$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

Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment