Advertisement
ec1117

Untitled

Jun 20th, 2020
132
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.97 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. InputReader in = new InputReader(new FileInputStream("6.in.txt"));
  16. PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(TASKNAME+".out")));
  17. Autocompletion solver = new Autocompletion();
  18. db=new Debug(System.getSecurityManager()==null);
  19. solver.solve(1, in, out);
  20. out.close();
  21. }
  22. static class Autocompletion {
  23. static ArrayList<Integer>[] ord;
  24. static int n;
  25. public void solve(int testNumber, InputReader in, PrintWriter out) {
  26. n=in.nextInt();
  27. int m=in.nextInt();
  28. ord=new ArrayList[m];
  29. ArrayList<Integer>[] adj=new ArrayList[n];
  30. for(int i=0;i<m;i++)ord[i]=new ArrayList<Integer>();
  31. for(int i=0;i<n;i++)adj[i]=new ArrayList<Integer>();
  32. for(int i=0;i<m;i++) {
  33. int x=in.nextInt();
  34. for(int j=0;j<x;j++) {
  35. ord[i].add(in.nextInt()-1);
  36. }
  37. }
  38. int l=0;
  39. int r=m;
  40. while(l!=r) {//bsearch for max
  41. int mid=l+(r-l+1)/2;
  42. if(works(mid)) {
  43. l=mid;
  44. }
  45. else {
  46. r=mid-1;
  47. }
  48. }
  49. for(int i=0;i<l;i++) {
  50. for(int j=1;j<ord[i].size();j++) {
  51. adj[ord[i].get(j-1)].add(ord[i].get(j));
  52. }
  53. }
  54. int count[]=new int[n];
  55. for(int i=0;i<l;i++) {
  56. for(int j=1;j<ord[i].size();j++) {
  57. count[ord[i].get(j)]++;
  58. }
  59. }
  60. PriorityQueue<Integer> dq=new PriorityQueue<Integer>();
  61. for(int i=0;i<n;i++) {
  62. if(count[i]==0) {
  63. dq.add(i);
  64. }
  65. }
  66. StringBuilder sb=new StringBuilder();
  67. while(!dq.isEmpty()) {
  68. int x=dq.remove();
  69. sb.append((x+1)+" ");
  70. for(int y:adj[x]) {
  71. count[y]--;
  72. if(count[y]==0) {
  73. dq.add(y);
  74. }
  75. }
  76. }
  77. out.println(sb.toString().trim());
  78. }
  79. private boolean works(int mid) {
  80. ArrayList<Integer>[] adj=new ArrayList[n];
  81. for(int i=0;i<n;i++)adj[i]=new ArrayList<Integer>();
  82. for(int i=0;i<mid;i++) {
  83. for(int j=1;j<ord[i].size();j++) {
  84. adj[ord[i].get(j-1)].add(ord[i].get(j));
  85. }
  86. }
  87. TreeSet<Integer> vis=new TreeSet<Integer>();
  88. TreeSet<Integer> left=new TreeSet<Integer>();
  89. for(int i=0;i<n;i++)left.add(i);
  90. ArrayDeque<Integer> dq=new ArrayDeque<Integer>();
  91. while(left.size()>0) {
  92. int first=left.pollFirst();
  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(x);
  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