题解 | #红和蓝#
红和蓝
https://www.nowcoder.com/practice/34bf2aaeb61f47be980b9ec0ab238c36
import java.util.*; public class Main { private static class Node{ List<Node> neighbor = new ArrayList<>(); Node pair = null; // 树中的结点是两两组队的,这里记录它的队友 char color = '_'; } private static boolean abort = false; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); Node[] nodes = new Node[n+1]; for(int i=1;i<=n;i++) nodes[i] = new Node(); for(int i=1;i<n;i++) { // 记录邻接信息 int l = sc.nextInt(); int k = sc.nextInt(); nodes[l].neighbor.add(nodes[k]); nodes[k].neighbor.add(nodes[l]); } getPairInfo(nodes[1],null); // 组队 if(!abort && nodes[1].pair != null){ paintColor(nodes[1],null); // 染色 for(int i=1;i<=n;i++) { System.out.print(nodes[i].color); } } else{ System.out.print(-1); } } private static void getPairInfo(Node root,Node father){ for(int i=0;i<root.neighbor.size();i++){ Node cur = root.neighbor.get(i); if(cur == father) continue; getPairInfo(cur,root);// 先更新子节点 if(abort) return; // 下层遍历如果发现无解则直接返回 if(cur.pair == null){ // 子节点pair为空,说明子节点需要和当前节点组队 if(root.pair != null){ // 子节点与当前节点组队发现此节点已经组队了,则无解,直接返回 abort = true; return; } cur.pair = root; root.pair = cur; } // 如果子节点已经组队了,那么此节点应该与其父节点组队,直接返回即可,故else为空 } } private static void paintColor(Node root,Node father){ if(father != null && father.pair == root){ root.color = father.color; } else { if(father != null) root.color = (father.color == 'B') ? 'R':'B'; else root.color = 'B'; } for(int i=0;i<root.neighbor.size();i++){ Node cur = root.neighbor.get(i); if(cur == father) continue; paintColor(cur,root); } } }
真不明白为什么这群写c++的,变量名也不好好取,也不写注释,代码可读性太差了
希望这篇回答会帮助正在尝试解题的你!