Cod sursa(job #1705917)

Utilizator bercarucostinBercaru Costin bercarucostin Data 21 mai 2016 07:30:53
Problema Sortare topologica Scor 80
Compilator java Status done
Runda Arhiva educationala Marime 1.92 kb
//package problemetest2;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;

public class Main {

	static ArrayList<ArrayList<Integer>> graf = new ArrayList<ArrayList<Integer>>();
	static int[] c;

	public static ArrayList<Integer> sort() {

		ArrayList<Integer> vs = new ArrayList<Integer>();
		for (int i = 1; i < graf.size(); i++) {
			System.out.println(i);
			if (c[i] == 0)
				vs = explore(i, vs);
		}

		return vs;
	}

	public static ArrayList<Integer> explore(int u, ArrayList<Integer> vs) {

		c[u] = 1;
		for (int v : graf.get(u)) {
			if (c[v] == 0)
				vs = explore(v, vs);
			else
				System.out.println("da da");
		}
		c[u] = 2;
		vs.add(u);
		return vs;

	}

	public static void main(String[] args) throws IOException {

		BufferedReader in = null;
		BufferedWriter out = null;
		in = new BufferedReader(new FileReader("sortaret.in"));
		out = new BufferedWriter(new FileWriter("sortaret.out"));

		String[] line = in.readLine().split(" ");
		int n = Integer.parseInt(line[0]);
		int m = Integer.parseInt(line[1]);
		c = new int[n + 1];

		for (int i = 0; i < n + 1; i++)
			graf.add(i, new ArrayList<Integer>());
		for (int i = 0; i < m; i++) {
			line = in.readLine().split(" ");

			graf.get(Integer.parseInt(line[0])).add(Integer.parseInt(line[1]));
			// graf.get(Integer.parseInt(line[1])).add(Integer.parseInt(line[0]));
		}
		for(int i = 1; i < graf.size(); i ++){
		//	for(int n2 : graf.get(i))
				System.out.println("Nodul " + i + " are drum pana la nodul " + " si are matricea de vecini size: " + graf.get(i).size());
		}
		ArrayList<Integer> rez = sort();
		System.out.println(rez.size());
		for(int i = rez.size() - 1; i >= 0; i --){
			System.out.println(rez.get(i));
			out.write(rez.get(i) + " ");
		}
		in.close();
		out.close();
	}
}