/* * Finding the paths between every possible pair of nodes on a tree * For each pair of node, this program will find the path that connects * them (back and forth) on any tree (not necessarily binary). All the paths * will be store on the subArrays member property of the TreeStruct class and the * full list of paths can be printed using the printPaths() method. * The input follows the following format: * - The first line is an integer N representing the number of nodes on the tree * - Next, there are N-1 lines with two space separeted integers u,v in each line * indicating that node u is connected to node v by an edge. * * i.e: for the following tree: * 1 * / \ * 2 3 * / \ * 4 5 * * The input will be: * 5 * 1 2 * 1 3 * 3 4 * 3 5 */ import java.io.*; import java.util.*; public class TreeStruct { Vector> edges; HashMap> subArrays; int nodes; TreeStruct(int numberOfNodes){ this.nodes = numberOfNodes; this.edges = new Vector>(); this.subArrays = new HashMap>(); for(int c_i = 0; c_i < this.nodes; c_i++){ this.edges.add(new LinkedList()); } } public void addEdge(int u, int v){ this.edges.elementAt(u).add(v); this.edges.elementAt(v).add(u); } private void generatePaths(){ for (int i = 0; i < this.nodes; ++i){ Vector visitedNodes = new Vector(); Vector pendingToVisit = new Vector(); visitedNodes.add(i); this.subArrays.put(i+" "+i,new Vector(visitedNodes)); int from = i, to = i; while (visitedNodes.size() < this.nodes){ Vector subArray = new Vector(this.subArrays.get(from+" "+to)); LinkedList unvisitedNodes = new LinkedList(this.edges.elementAt(to)); unvisitedNodes.removeAll(visitedNodes); Iterator it = unvisitedNodes.iterator(); while (it.hasNext()){ int next = it.next(); pendingToVisit.add(next); subArray.add(next); visitedNodes.add(next); this.subArrays.put(i+" "+next,new Vector(subArray)); subArray.remove(new Integer(next)); } if (!pendingToVisit.isEmpty()){ to = (int)pendingToVisit.lastElement(); pendingToVisit.remove(pendingToVisit.lastElement()); } else{ break; } } } } public void printPaths(){ if (this.subArrays.isEmpty()){ this.generatePaths(); } Iterator>> it = this.subArrays.entrySet().iterator(); while (it.hasNext()) { Map.Entry> entry = it.next(); String st = entry.getKey(); System.out.print("From Node " + ((int)st.charAt(0)-47) + " to Node " + ((int)st.charAt(2)-47) + ": ["); Iterator nodeIter = entry.getValue().iterator(); while (nodeIter.hasNext()){ System.out.print(nodeIter.next()+1); if (nodeIter.hasNext()){ System.out.print("-"); } } System.out.println("]"); } } } public class Program { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); TreeStruct tree = new TreeStruct(n); for (int i = 0; i < (n-1); ++i){ int u = sc.nextInt()-1; int v = sc.nextInt()-1; tree.addEdge(u,v); } sc.close(); tree.printPaths(); } }