Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.lang.*;
- import java.math.*;
- import java.util.*;
- import javax.rmi.CORBA.Util;
- public class Main {
- int n, k = 0, comps = 0;
- Vektor[] g, bg;
- boolean[] u;
- int[] comp, ls, ind;
- public void solve() throws IOException {
- n = nextInt();
- g = new Vektor[n];
- bg = new Vektor[n];
- for (int i = 0; i < n; i++) {
- g[i] = new Vektor(n);
- bg[i] = new Vektor(n);
- }
- for (int i = 0; i < n; i++) {
- int x = nextInt();
- while (x > 0) {
- g[i].add(x - 1);
- bg[x - 1].add(i);
- x = nextInt();
- }
- }
- u = new boolean[n];
- comp = new int[n];
- ls = new int[n];
- ind = new int[n];
- for (int i = 0; i < n; i++)
- if (!u[i])
- dfs(i);
- Arrays.fill(u, false);
- for (int i = n - 1; i >= 0; i--)
- if (!u[ls[i]])
- col(ls[i], comps++);
- for (int i = 0; i < n; i++)
- for (int _ = 0, j = g[i].body[_]; _ < g[i].cnt; j = g[i].body[++_])
- if (comp[i] != comp[j]) {
- ind[comp[j]]++;
- // out.println(" >> " + comp[j]);
- }
- int cnt = 0, f = -1;
- for (int i = 0; i < comps; i++)
- if (ind[i] == 0) {
- cnt++; f = i;
- }
- if (cnt == 1)
- for (int i = 0; i < n; i++)
- if (comp[i] == f)
- out.print((i + 1) + " ");
- out.println(0);
- }
- void dfs(int v) {
- u[v] = true;
- for (int _ = 0, to = g[v].body[_]; _ < g[v].cnt; to = g[v].body[++_])
- if (!u[to])
- dfs(to);
- ls[k++] = v;
- }
- void col(int v, int color) {
- u[v] = true;
- comp[v] = color;
- // out.print("color of " + v + " is " + color + "\n");
- for (int _ = 0, to = bg[v].body[_]; _ < bg[v].cnt; to = bg[v].body[++_])
- if (!u[to])
- col(to, color);
- }
- public void run() throws IOException {
- boolean STDIO = true;
- // STDIO = false;
- tok = new StringTokenizer("");
- if (STDIO) {
- in = new BufferedReader(new InputStreamReader(System.in));
- out = new PrintWriter(System.out);
- } else {
- in = new BufferedReader(new FileReader("input.txt"));
- out = new PrintWriter(new File("output.txt"));
- }
- solve();
- out.close();
- }
- public static void main(String[] args) throws IOException {
- new Main().run();
- }
- String nextToken() throws IOException {
- while (!tok.hasMoreTokens())
- tok = new StringTokenizer(in.readLine());
- return tok.nextToken();
- }
- int nextInt() throws IOException {
- return Integer.parseInt(nextToken());
- }
- long nextLong() throws IOException {
- return Long.parseLong(nextToken());
- }
- double nextDouble() throws IOException {
- return Double.parseDouble(nextToken());
- }
- static class Vektor {
- int[] body;
- int cnt;
- Vektor(int size) {
- body = new int[size];
- cnt = 0;
- } // Vektor
- void add(int v) {
- body[cnt++] = v;
- } // add
- } // Vektor
- BufferedReader in;
- StringTokenizer tok;
- PrintWriter out;
- }
Advertisement
Add Comment
Please, Sign In to add comment