Guest User

Untitled

a guest
Nov 27th, 2011
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.85 KB | None | 0 0
  1. import java.io.*;
  2. import java.lang.*;
  3. import java.math.*;
  4. import java.util.*;
  5.  
  6. import javax.rmi.CORBA.Util;
  7.  
  8. public class Main {
  9. int n, k = 0, comps = 0;
  10. Vektor[] g, bg;
  11. boolean[] u;
  12. int[] comp, ls, ind;
  13.  
  14. public void solve() throws IOException {
  15. n = nextInt();
  16. g = new Vektor[n];
  17. bg = new Vektor[n];
  18. for (int i = 0; i < n; i++) {
  19. g[i] = new Vektor(n);
  20. bg[i] = new Vektor(n);
  21. }
  22.  
  23. for (int i = 0; i < n; i++) {
  24. int x = nextInt();
  25. while (x > 0) {
  26. g[i].add(x - 1);
  27. bg[x - 1].add(i);
  28. x = nextInt();
  29. }
  30. }
  31.  
  32. u = new boolean[n];
  33. comp = new int[n];
  34. ls = new int[n];
  35. ind = new int[n];
  36.  
  37. for (int i = 0; i < n; i++)
  38. if (!u[i])
  39. dfs(i);
  40.  
  41. Arrays.fill(u, false);
  42. for (int i = n - 1; i >= 0; i--)
  43. if (!u[ls[i]])
  44. col(ls[i], comps++);
  45.  
  46. for (int i = 0; i < n; i++)
  47. for (int _ = 0, j = g[i].body[_]; _ < g[i].cnt; j = g[i].body[++_])
  48. if (comp[i] != comp[j]) {
  49. ind[comp[j]]++;
  50. // out.println(" >> " + comp[j]);
  51. }
  52.  
  53. int cnt = 0, f = -1;
  54. for (int i = 0; i < comps; i++)
  55. if (ind[i] == 0) {
  56. cnt++; f = i;
  57. }
  58.  
  59. if (cnt == 1)
  60. for (int i = 0; i < n; i++)
  61. if (comp[i] == f)
  62. out.print((i + 1) + " ");
  63.  
  64. out.println(0);
  65. }
  66.  
  67. void dfs(int v) {
  68. u[v] = true;
  69. for (int _ = 0, to = g[v].body[_]; _ < g[v].cnt; to = g[v].body[++_])
  70. if (!u[to])
  71. dfs(to);
  72. ls[k++] = v;
  73. }
  74.  
  75. void col(int v, int color) {
  76. u[v] = true;
  77. comp[v] = color;
  78. // out.print("color of " + v + " is " + color + "\n");
  79. for (int _ = 0, to = bg[v].body[_]; _ < bg[v].cnt; to = bg[v].body[++_])
  80. if (!u[to])
  81. col(to, color);
  82. }
  83.  
  84. public void run() throws IOException {
  85. boolean STDIO = true;
  86. // STDIO = false;
  87. tok = new StringTokenizer("");
  88. if (STDIO) {
  89. in = new BufferedReader(new InputStreamReader(System.in));
  90. out = new PrintWriter(System.out);
  91. } else {
  92. in = new BufferedReader(new FileReader("input.txt"));
  93. out = new PrintWriter(new File("output.txt"));
  94. }
  95. solve();
  96. out.close();
  97. }
  98.  
  99. public static void main(String[] args) throws IOException {
  100. new Main().run();
  101. }
  102.  
  103. String nextToken() throws IOException {
  104. while (!tok.hasMoreTokens())
  105. tok = new StringTokenizer(in.readLine());
  106. return tok.nextToken();
  107. }
  108.  
  109. int nextInt() throws IOException {
  110. return Integer.parseInt(nextToken());
  111. }
  112.  
  113. long nextLong() throws IOException {
  114. return Long.parseLong(nextToken());
  115. }
  116.  
  117. double nextDouble() throws IOException {
  118. return Double.parseDouble(nextToken());
  119. }
  120.  
  121. static class Vektor {
  122. int[] body;
  123. int cnt;
  124.  
  125. Vektor(int size) {
  126. body = new int[size];
  127. cnt = 0;
  128. } // Vektor
  129.  
  130. void add(int v) {
  131. body[cnt++] = v;
  132. } // add
  133. } // Vektor
  134.  
  135.  
  136. BufferedReader in;
  137. StringTokenizer tok;
  138. PrintWriter out;
  139. }
  140.  
  141.  
Advertisement
Add Comment
Please, Sign In to add comment