题解 | 红和蓝-双向图建模

如果把路径看作单向的，这道题的输入疑似不保证树可以由一个根结点出发访问到所有的节点，我测试会有很多个入度为0的节点

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    private static HashMap<Integer, Integer> map = new
    HashMap<>(); //记录组队关系
    private static ArrayList<ArrayList<Integer>> tree = new ArrayList<>();
    private static boolean canfind = true;
    private static int root;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();

        for (int i = 0; i <= n; i++) tree.add(new ArrayList<>());
        HashSet<Integer> roots = new HashSet<>();
        for (int i = 1; i <= n; i++) roots.add(i);
        int u, v;
        for (int i = 0; i < n - 1; i++) {
            u = in.nextInt();
            v = in.nextInt();
            tree.get(u).add(v);
            tree.get(v).add(u);
            roots.remove(v);
        }
        int treeRoot = 1;
        for(int key:roots) treeRoot =  key;
        dfs(treeRoot,0);

        if (!canfind) System.out.println(-1);
        else {
            //开始染色
            char[] RB = new char[n + 1];
            Arrays.fill(RB, 'n');
            dfs2(treeRoot, RB, 0);
            for (int i = 1; i <= n; i++)
                System.out.print(RB[i]);
        }
    }

    public static void dfs2(int curNode, char[] RB, int rootOfCurNode) {
        if (RB[curNode] == 'n') {
            if (RB[rootOfCurNode] == 'R') {
                RB[curNode] = 'B';
                RB[map.get(curNode)] = 'B';
            } else {
                RB[curNode] = 'R';
                RB[map.get(curNode)] = 'R';
            }
        }

        for (int nextNode : tree.get(curNode)) {
            if (nextNode == rootOfCurNode) continue;
            dfs2(nextNode, RB, curNode);
        }
    }

    public static void dfs(int curNode, int parent) {
        if (!map.containsKey(curNode)) {
            boolean flag = false;
            for (int node : tree.get(curNode)) {
                if (!map.containsKey(node)) {
                    map.put(node, curNode);
                    map.put(curNode, node);
                    flag = true;
                    break;
                }
            }
            if (!flag) canfind = false;
        }
        if (canfind) {
            for (int nextNode : tree.get(curNode)) {
                if (nextNode == parent) continue;
                dfs(nextNode, curNode);
            }
        }
    }
}