I am trying to solve following problem.
Any hint and more better a solution is appreciated. I am trying a lot but not solved yet.
My New Code
package com.onssoftware;
import java.io.*; import java.util.*;
public class A2_Uprooted {
public static Kattio io; public static void main(String[] args) { io = new Kattio(System.in, System.out); int N = io.getInt(); int M = io.getInt(); int S = io.getInt(); Map<Integer, List<Edge>> adjList = new HashMap<>(); for (int index = 1; index <= M; index++) { int a = io.getInt(); int b = io.getInt(); int c = io.getInt(); Edge e = new Edge(a, b, c, index); List<Edge> listA = adjList.getOrDefault(a, new ArrayList<>()); listA.add(e); adjList.put(a, listA); List<Edge> listB = adjList.getOrDefault(b, new ArrayList<>()); listB.add(e); adjList.put(b, listB); } int[][] sequences = new int[S][N - 1]; for (int i = 0; i < S; i++) { for (int j = 0; j < N - 1; j++) { sequences[i][j] = io.getInt(); } } new A2_Uprooted().solution(N, M, S, adjList, sequences); io.close(); } public void solution(int n, int m, int s, Map<Integer, List<Edge>> adjList, int[][] sequences) { Map<Integer, Set<Edge>> nodeListMap = new HashMap<>(); StringBuilder stringbuilder = new StringBuilder(); for (int row = 0; row < s; row++) { Map<Integer, Boolean> nodeMap = new HashMap<>(); // Node 1 is taken nodeMap.put(1, true); for (int column = 0; column < n - 1; column++) { int node = sequences[row][column]; if (nodeMap.getOrDefault(node, false)) continue; // List<Edge> edgeList = adjList.getOrDefault(node, new ArrayList<>()); Set<Edge> tempList = new HashSet<>(); for (Edge edge : edgeList) { // Add node to existing set int neighbour = edge.getNeighbour(node); // If any of neighbours in the set, and if so, we consider it, add it to all existing edges if (nodeMap.getOrDefault(neighbour, false)) { //tempList is the primary options tempList.add(edge); } } // Fetch the old options from previous sequences Set<Edge> nodeListOld = nodeListMap.getOrDefault(node, new HashSet<>()); // Check if any common branches. Then remove it. getCommon is a must have Set<Edge> nodeListCommon = getCommon(nodeListOld, tempList); // If there are no common branches, then its impossilbe if (nodeListCommon.isEmpty()) { io.println("IMPOSSIBLE"); return; } // Saving the options to add nodes to existing vertices. Considering all common edges nodeListMap.put(node, nodeListCommon); // Add the new vertex into the nodemap nodeMap.put(node, true); } } List<Edge> edgeListFinal = new ArrayList<>(); // Constructing the solutions for (Integer node : nodeListMap.keySet()) { Set<Edge> edgeList = nodeListMap.getOrDefault(node, new HashSet<>()); if (edgeList.size() == 1) { edgeListFinal.addAll(edgeList); } else { Edge maxEdge = null; for (Edge e : edgeList) { if (maxEdge == null || maxEdge.c < e.c) // Adding all the maximum edges. maxEdge = e; } edgeListFinal.add(maxEdge); } } io.println(edgeListFinal.size()); for (int i = 0; i < edgeListFinal.size() - 1; i++) { stringbuilder.append(edgeListFinal.get(i).index).append(" "); // io.print(edgeListFinal.get(i).index + " "); } io.print(stringbuilder.toString()); io.println(edgeListFinal.get(edgeListFinal.size() - 1).index); } private Set<Edge> getCommon(Set<Edge> nodeListOld, Set<Edge> tempList) { if (nodeListOld.isEmpty()) return new HashSet<>(tempList); nodeListOld.retainAll(tempList); return nodeListOld; }
}
class Edge { int a, b, c, index;
Edge(int a, int b, int c, int index) { this.a = a; this.b = b; this.c = c; this.index = index; } int getNeighbour(int one) { if (a == one) return b; return a; }
}
class Kattio extends PrintWriter { private BufferedReader r; private String line; private StringTokenizer st; private String token;
public Kattio(InputStream i) { super(new BufferedOutputStream(System.out)); r = new BufferedReader(new InputStreamReader(i)); } public Kattio(InputStream i, OutputStream o) { super(new BufferedOutputStream(o)); r = new BufferedReader(new InputStreamReader(i)); } public boolean hasMoreTokens() { return peekToken() != null; } public int getInt() { return Integer.parseInt(nextToken()); } public double getDouble() { return Double.parseDouble(nextToken()); } public long getLong() { return Long.parseLong(nextToken()); } public String getWord() { return nextToken(); } private String peekToken() { if (token == null) try { while (st == null || !st.hasMoreTokens()) { line = r.readLine(); if (line == null) return null; st = new StringTokenizer(line); } token = st.nextToken(); } catch (IOException e) { } return token; } private String nextToken() { String ans = peekToken(); token = null; return ans; }
}
or you can use some other websites like ideone
By the way, I am unable to see the problem :(
See now please.
Also, doing this to have highlighting code
```cpp
```
If S=0, we are finding a MST
Instead of an rooted undirected tree, think the result tree as a direct tree starting from root.
s >= 1 so no MST I think. Now trying to make some edge set from sequence 1. Then When i process seq 2, trying to filter previous choices. What do you think?
The solution I have in mind is really close to MST
Also the number of possible edge set can be exponential
Fix a good tree T. if $$$u$$$ is $$$v$$$'s immediate parent, what does that imply in each of the $$$S$$$ sequences?
I applied some edge fixing. Passed 4 cases then TLE. See my updated code on the message.
As discussed your solution won't likely work :(
Your solution works in $$$O(S(N+M))$$$ which is probably too slow