Advertisement
ec1117

Untitled

Jun 20th, 2020
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.93 KB | None | 0 0
  1. import java.util.*;
  2. import java.io.*;
  3. import java.io.BufferedReader;
  4. import java.awt.Point;
  5.  
  6. public class milkorder{
  7. public static final String TASKNAME = "milkorder";
  8. public static long mod= 1000000007;
  9. public static Debug db;
  10.  
  11. public static void main(String[] args) throws IOException {
  12. // InputReader in = new InputReader(System.in);
  13. // PrintWriter out = new PrintWriter(System.out);
  14. InputReader in = new InputReader(new FileInputStream(TASKNAME+".in"));
  15. PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(TASKNAME+".out")));
  16. Autocompletion solver = new Autocompletion();
  17. db=new Debug(System.getSecurityManager()==null);
  18. solver.solve(1, in, out);
  19. out.close();
  20. }
  21. static class Autocompletion {
  22. static ArrayList<Integer>[] ord;
  23. static int n;
  24. public void solve(int testNumber, InputReader in, PrintWriter out) {
  25. n=in.nextInt();
  26. int m=in.nextInt();
  27. ord=new ArrayList[m];
  28. ArrayList<Integer>[] adj=new ArrayList[n];
  29. for(int i=0;i<m;i++)ord[i]=new ArrayList<Integer>();
  30. for(int i=0;i<n;i++)adj[i]=new ArrayList<Integer>();
  31. for(int i=0;i<m;i++) {
  32. int x=in.nextInt();
  33. for(int j=0;j<x;j++) {
  34. ord[i].add(in.nextInt()-1);
  35. }
  36. }
  37. int l=0;
  38. int r=m;
  39. while(l!=r) {//bsearch for max
  40. int mid=l+(r-l+1)/2;
  41. if(works(mid)) {
  42. l=mid;
  43. }
  44. else {
  45. r=mid-1;
  46. }
  47. }
  48. for(int i=0;i<l;i++) {
  49. for(int j=1;j<ord[i].size();j++) {
  50. adj[ord[i].get(j-1)].add(ord[i].get(j));
  51. }
  52. }
  53. int count[]=new int[n];
  54. for(int i=0;i<l;i++) {
  55. for(int j=1;j<ord[i].size();j++) {
  56. count[ord[i].get(j)]++;
  57. }
  58. }
  59. PriorityQueue<Integer> dq=new PriorityQueue<Integer>();
  60. for(int i=0;i<n;i++) {
  61. if(count[i]==0) {
  62. dq.add(i);
  63. }
  64. }
  65. StringBuilder sb=new StringBuilder();
  66. while(!dq.isEmpty()) {
  67. int x=dq.remove();
  68. sb.append((x+1)+" ");
  69. for(int y:adj[x]) {
  70. count[y]--;
  71. if(count[y]==0) {
  72. dq.add(y);
  73. }
  74. }
  75. }
  76. out.println(sb.toString().trim());
  77. }
  78. private boolean works(int mid) {
  79. ArrayList<Integer>[] adj=new ArrayList[n];
  80. for(int i=0;i<n;i++)adj[i]=new ArrayList<Integer>();
  81. for(int i=0;i<mid;i++) {
  82. for(int j=1;j<ord[i].size();j++) {
  83. adj[ord[i].get(j-1)].add(ord[i].get(j));
  84. }
  85. }
  86. TreeSet<Integer> vis=new TreeSet<Integer>();
  87. TreeSet<Integer> left=new TreeSet<Integer>();
  88. for(int i=0;i<n;i++)left.add(i);
  89. ArrayDeque<Integer> dq=new ArrayDeque<Integer>();
  90. while(left.size()>0) {
  91. int first=left.pollFirst();
  92. left.remove(first);
  93. dq.add(first);
  94. TreeSet<Integer> visnow=new TreeSet<Integer>();
  95. while(!dq.isEmpty()) {
  96. int x=dq.remove();
  97. visnow.add(x);
  98. left.remove(first);
  99. vis.add(x);
  100. for(int y:adj[x]) {
  101. if(visnow.contains(y)) {
  102. return false;
  103. }
  104. if(!vis.contains(y)) {
  105. dq.add(y);
  106. }
  107. }
  108. }
  109. }
  110. return true;
  111. }
  112. }
  113.  
  114. static class InputReader {
  115. public BufferedReader reader;
  116. public StringTokenizer tokenizer;
  117.  
  118. public InputReader(InputStream stream) {
  119. reader = new BufferedReader(new InputStreamReader(stream), 32768);
  120. tokenizer = null;
  121. }
  122.  
  123. public String next() {
  124. while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  125. try {
  126. tokenizer = new StringTokenizer(reader.readLine());
  127. } catch (IOException e) {
  128. throw new RuntimeException(e);
  129. }
  130. }
  131. return tokenizer.nextToken();
  132. }
  133.  
  134. public int nextInt() {
  135. return Integer.parseInt(next());
  136. }
  137. public long nextLong() {
  138. return Long.parseLong(next());
  139. }
  140. public int[] nextIntArr(int n) {
  141. int arr[]=new int[n];
  142. for(int i=0;i<n;i++) {
  143. arr[i]=this.nextInt();
  144. }
  145. return arr;
  146. }
  147. }
  148. public static class Debug {
  149. private boolean allowDebug;
  150.  
  151. public Debug(boolean allowDebug) {
  152. this.allowDebug = allowDebug;
  153. }
  154.  
  155. private void outputName(String name) {
  156. System.out.print(name + " = ");
  157. }
  158.  
  159. public void debug(String name, int x) {
  160. if (!allowDebug) {
  161. return;
  162. }
  163.  
  164. outputName(name);
  165. System.out.println("" + x);
  166. }
  167.  
  168. public void debug(String name, long x) {
  169. if (!allowDebug) {
  170. return;
  171. }
  172. outputName(name);
  173. System.out.println("" + x);
  174. }
  175.  
  176. public void debug(String name, double x) {
  177. if (!allowDebug) {
  178. return;
  179. }
  180. outputName(name);
  181. System.out.println("" + x);
  182. }
  183.  
  184. public void debug(String name, int[] x) {
  185. if (!allowDebug) {
  186. return;
  187. }
  188. outputName(name);
  189. System.out.println(Arrays.toString(x));
  190. }
  191.  
  192. public void debug(String name, long[] x) {
  193. if (!allowDebug) {
  194. return;
  195. }
  196. outputName(name);
  197. System.out.println(Arrays.toString(x));
  198. }
  199.  
  200. public void debug(String name, double[] x) {
  201. if (!allowDebug) {
  202. return;
  203. }
  204. outputName(name);
  205. System.out.println(Arrays.toString(x));
  206. }
  207.  
  208. public void debug(String name, Object x) {
  209. if (!allowDebug) {
  210. return;
  211. }
  212. outputName(name);
  213. System.out.println("" + x);
  214. }
  215.  
  216. public void debug(String name, Object... x) {
  217. if (!allowDebug) {
  218. return;
  219. }
  220. outputName(name);
  221. System.out.println(Arrays.deepToString(x));
  222. }
  223. }
  224. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement