Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.io.*;
- import java.io.BufferedReader;
- import java.awt.Point;
- public class milkorder{
- public static final String TASKNAME = "milkorder";
- public static long mod= 1000000007;
- public static Debug db;
- public static void main(String[] args) throws IOException {
- // InputReader in = new InputReader(System.in);
- // PrintWriter out = new PrintWriter(System.out);
- // InputReader in = new InputReader(new FileInputStream(TASKNAME+".in"));
- InputReader in = new InputReader(new FileInputStream("6.in.txt"));
- PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(TASKNAME+".out")));
- Autocompletion solver = new Autocompletion();
- db=new Debug(System.getSecurityManager()==null);
- solver.solve(1, in, out);
- out.close();
- }
- static class Autocompletion {
- static ArrayList<Integer>[] ord;
- static int n;
- public void solve(int testNumber, InputReader in, PrintWriter out) {
- n=in.nextInt();
- int m=in.nextInt();
- ord=new ArrayList[m];
- ArrayList<Integer>[] adj=new ArrayList[n];
- for(int i=0;i<m;i++)ord[i]=new ArrayList<Integer>();
- for(int i=0;i<n;i++)adj[i]=new ArrayList<Integer>();
- for(int i=0;i<m;i++) {
- int x=in.nextInt();
- for(int j=0;j<x;j++) {
- ord[i].add(in.nextInt()-1);
- }
- }
- int l=0;
- int r=m;
- while(l!=r) {//bsearch for max
- int mid=l+(r-l+1)/2;
- if(works(mid)) {
- l=mid;
- }
- else {
- r=mid-1;
- }
- }
- for(int i=0;i<l;i++) {
- for(int j=1;j<ord[i].size();j++) {
- adj[ord[i].get(j-1)].add(ord[i].get(j));
- }
- }
- int count[]=new int[n];
- for(int i=0;i<l;i++) {
- for(int j=1;j<ord[i].size();j++) {
- count[ord[i].get(j)]++;
- }
- }
- PriorityQueue<Integer> dq=new PriorityQueue<Integer>();
- for(int i=0;i<n;i++) {
- if(count[i]==0) {
- dq.add(i);
- }
- }
- StringBuilder sb=new StringBuilder();
- while(!dq.isEmpty()) {
- int x=dq.remove();
- sb.append((x+1)+" ");
- for(int y:adj[x]) {
- count[y]--;
- if(count[y]==0) {
- dq.add(y);
- }
- }
- }
- out.println(sb.toString().trim());
- }
- private boolean works(int mid) {
- ArrayList<Integer>[] adj=new ArrayList[n];
- for(int i=0;i<n;i++)adj[i]=new ArrayList<Integer>();
- for(int i=0;i<mid;i++) {
- for(int j=1;j<ord[i].size();j++) {
- adj[ord[i].get(j-1)].add(ord[i].get(j));
- }
- }
- TreeSet<Integer> vis=new TreeSet<Integer>();
- TreeSet<Integer> left=new TreeSet<Integer>();
- for(int i=0;i<n;i++)left.add(i);
- ArrayDeque<Integer> dq=new ArrayDeque<Integer>();
- while(left.size()>0) {
- int first=left.pollFirst();
- dq.add(first);
- TreeSet<Integer> visnow=new TreeSet<Integer>();
- while(!dq.isEmpty()) {
- int x=dq.remove();
- visnow.add(x);
- left.remove(x);
- vis.add(x);
- for(int y:adj[x]) {
- if(visnow.contains(y)) {
- return false;
- }
- if(!vis.contains(y)) {
- dq.add(y);
- }
- }
- }
- }
- return true;
- }
- }
- static class InputReader {
- public BufferedReader reader;
- public StringTokenizer tokenizer;
- public InputReader(InputStream stream) {
- reader = new BufferedReader(new InputStreamReader(stream), 32768);
- tokenizer = null;
- }
- public String next() {
- while (tokenizer == null || !tokenizer.hasMoreTokens()) {
- try {
- tokenizer = new StringTokenizer(reader.readLine());
- } catch (IOException e) {
- throw new RuntimeException(e);
- }
- }
- return tokenizer.nextToken();
- }
- public int nextInt() {
- return Integer.parseInt(next());
- }
- public long nextLong() {
- return Long.parseLong(next());
- }
- public int[] nextIntArr(int n) {
- int arr[]=new int[n];
- for(int i=0;i<n;i++) {
- arr[i]=this.nextInt();
- }
- return arr;
- }
- }
- public static class Debug {
- private boolean allowDebug;
- public Debug(boolean allowDebug) {
- this.allowDebug = allowDebug;
- }
- private void outputName(String name) {
- System.out.print(name + " = ");
- }
- public void debug(String name, int x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println("" + x);
- }
- public void debug(String name, long x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println("" + x);
- }
- public void debug(String name, double x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println("" + x);
- }
- public void debug(String name, int[] x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println(Arrays.toString(x));
- }
- public void debug(String name, long[] x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println(Arrays.toString(x));
- }
- public void debug(String name, double[] x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println(Arrays.toString(x));
- }
- public void debug(String name, Object x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println("" + x);
- }
- public void debug(String name, Object... x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println(Arrays.deepToString(x));
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement