In this problem you are given N sequences of distinct numbers. The task is to construct the shortest sequence S, such that all N sequences are (not necessarily continuous) subsequences of S. If there are many such sequences, then you have to construct the lexicographically smallest one. It is guaranteed that such a sequence exists. Sequence A[1……

FavSeq.java

import java.io.File;
import java.io.FileInputStream;
import java.io.InputStream;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class ProblemC {

		private static final int maxn = 1000000;

		private static final class EdgeNode {

			public int y;
			public EdgeNode edge;

			public EdgeNode(int y) {
				this.y = y;
				this.edge = null;
			}
		}

		private static class Graph {

			public final EdgeNode[] adj;
			public final int[] parent;
			public final Set<Integer> vertices;
			public final Set<Integer>[] vadj;
			public final int[] indegree;
			public final int[] outdegree;
			public final boolean[] processed;
			public final boolean directed;

			public Graph(boolean directed) {
				this.adj = new EdgeNode[maxn + 1];
				this.parent = new int[maxn + 1];
				this.vertices = new TreeSet<Integer>();
				this.indegree = new int[maxn + 1];
				this.outdegree = new int[maxn + 1];
				this.processed = new boolean[maxn + 1];
				this.vadj = new Set[maxn];
				this.directed = directed;
			}

			public void insertEdge(int x, int y, boolean directed) {
				vertices.add(x);
				vertices.add(y);
				
				vadj[x].add(y);
				outdegree[x]++;
				indegree[y]++;
				parent[y] = x;

				// initialize edge set E
				if (adj[x] == null) {
					adj[x] = new EdgeNode(y);

				} else {

					EdgeNode e = new EdgeNode(y);
					e.edge = adj[x];
					adj[x] = e;
				}

				if (!directed) {
					insertEdge(y, x, true);
				}

			}

			public Set<Integer> getLeaves() {
				Set<Integer> leaves = new HashSet<Integer>();
				
				for (Integer v : vertices) {
					if (indegree[v] == 0 && !processed[v]) {
						leaves.add(v);
						processed[v] = true;
					}
				}

				return leaves;
			}
		}

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

		int n = in.nextInt();

		Graph g = new Graph(true);

		for (int i = 0; i < n; i++) {
			int k = in.nextInt();

			int[] m = new int[k];
			for (int j = 0; j < k; j++) {
				m[j] = in.nextInt();
			}

			for (int j = 0; j < k - 1; j++) {
				if(g.vadj[m[j]] == null){
					g.vadj[m[j]] = new HashSet<Integer>();
				}
				
				if(!g.vadj[m[j]].contains(m[j + 1])){
					g.insertEdge(m[j], m[j + 1], true);
				}
			}
		}

		in.close();

		PriorityQueue<Integer> pq = new PriorityQueue<Integer>(n);

		for (Integer l : g.getLeaves()) {
			pq.offer(l);
		}

		Set<Integer> original = new LinkedHashSet<Integer>();
		
		//( (n*k) * (log n + deg(v)) )
		while (!pq.isEmpty()) {
			int v = pq.poll();

			if (!original.contains(v)) {
				original.add(v);
				System.out.printf("%d ", v);
			}

			EdgeNode e = g.adj[v];
			while(e != null){
				g.indegree[e.y]--;
                
				if(g.indegree[e.y] == 0 && !g.processed[e.y]){
					pq.offer(e.y);
					
					g.processed[e.y] = true;
				}
				
				e = e.edge;
			}
		}
	}
}