Search
Viz Zadání.
Úloha chce, abychom v obecném kořenovém stromu s obarvenými uzly našli co nejdelší monochromatickou cestu.
Myšlenka řešení:
Průchod postorder, v každém uzlu shromažďujeme informaci o délkách monochromatických cest vedoucích zespoda do tohoto uzlu, a to pouze o těch, jejichž barva souhlasí s barvou aktuálního uzlu. Pokud nám vychází cesta dosud nejdelší, zapamatujeme si ji. Tato nejdelší se skládá buď ze dvou větví vycházejících dolů z tohoto uzlu nebo z větve jediné. Délku nejdelší monochromatické větve té barvy, kterou má rodič, pošleme v postrorderu nahoru do rodiče.
Strom není nutno stavět, je reprezentován vhodně pro průchod postorder rovnou ve vstupních datech.
package alg; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.HashSet; import java.util.List; import java.util.Set; import java.util.StringTokenizer; public class Main { static Node root; static int bestLength; static Set<Integer> bestAttrs; public static class Node { int attr; int localBest; int directBest; int numOfNodes; List<Node> children; public Node(int attr) { this.attr = attr; localBest = 0; directBest = 0; numOfNodes = 0; children = new ArrayList<Node>(); } } private static void loadChildren(Node node, BufferedReader reader) throws IOException { StringTokenizer tokenizer = new StringTokenizer(reader.readLine()); String str = tokenizer.nextToken(); while (!str.equals(")")) { int attr = Integer.valueOf(str); Node child = new Node(attr); node.children.add(child); loadChildren(child, reader); tokenizer = new StringTokenizer(reader.readLine()); str = tokenizer.nextToken(); } } public static void loadData() throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer tokenizer = new StringTokenizer(reader.readLine()); String str = tokenizer.nextToken(); int attr = Integer.valueOf(str); root = new Node(attr); loadChildren(root, reader); } public static void postOrder(Node node) { int first = 0; int second = 0; node.numOfNodes = 1; for (Node child : node.children) { postOrder(child); if (child.attr == node.attr) { if (child.directBest > first) { second = first; first = child.directBest; } else if (child.directBest > second) { second = child.directBest; } } node.numOfNodes += child.numOfNodes; } node.localBest = 1 + first + second; node.directBest = 1 + first; if (node.localBest > bestLength) { bestAttrs.clear(); bestLength = node.localBest; bestAttrs.add(node.attr); } else if (node.localBest == bestLength) { bestAttrs.add(node.attr); } } public static void solve() { bestLength = 0; bestAttrs = new HashSet<Integer>(); postOrder(root); System.out.println(bestLength); List<Integer> bestAttrsList = new ArrayList<Integer>(bestAttrs); Collections.sort(bestAttrsList); for (int i = 0; i < bestAttrsList.size(); i++) { System.out.print(bestAttrsList.get(i)); if (i < bestAttrsList.size() - 1) System.out.print(" "); } } public static void main(String[] args) throws IOException { loadData(); solve(); } }