Cod sursa(job #1431260)

Utilizator serbanalex2202Serban Alexandru serbanalex2202 Data 9 mai 2015 09:12:03
Problema Sortare topologica Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.6 kb
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;

class Nod {
	public int id;
	int cost = -1; // cost pana aici pentru bfs cand o muchie costa 1
	int timp; // timp de atingere
	public boolean viz;
	public ArrayList<Nod> vecini = new ArrayList<Nod>();

	// public ArrayList<Integer> costuri = new ArrayList<Integer>();

	public Nod(int id) {
		super();
		this.id = id; // TODO ATENTI aici era +1 inainte
		this.viz = false;
	}

	@Override
	public String toString() {
		return "" + this.id;
	}

}

public class Main {

	public static int timp, nr_ctc;
	public static Stack<Nod> stack = new Stack<Nod>();

	// public static ArrayList<ArrayList<Nod>> ctcuri = new ArrayList<ArrayList<Nod>>();
	public static LinkedList<Nod> s = new LinkedList<Nod>();

	public static void main(String[] args) throws FileNotFoundException {
		PrintWriter writer = new PrintWriter(new FileOutputStream("sortaret.out"));
		ArrayList<Nod> g = new ArrayList<Nod>();
		readData(g);
		// afiG(g);
		for (Nod nod : g) {
			if (nod.viz == false) {
				DFS(g, nod);
			}
		}

		while (!stack.isEmpty()) {
			int u = s.pop().id + 1;
			writer.write(u + " ");
		}

		writer.close();
	}

	// topsort recursiv
	public static void DFS(ArrayList<Nod> g, Nod curent) {

		curent.viz = true;
		// parcurgem toate nodurile din graf - pentru fiecare nod incercam DFS
		for (Nod vecin : curent.vecini) {
			if (vecin.viz == false) {
				DFS(g, vecin);
			}
		}
		s.add(curent);
	}

	public static void readData(ArrayList<Nod> g) throws FileNotFoundException {
		int noduri;
		int muchii;

		Scanner s = new Scanner(new FileInputStream("sortaret.in"));

		noduri = s.nextInt();
		muchii = s.nextInt();

		for (int i = 0; i < noduri; i++) {

			g.add(new Nod(i));
		}

		for (int i = 0; i < muchii; i++) {
			int nod1 = s.nextInt() - 1;
			int nod2 = s.nextInt() - 1;
			g.get(nod1).vecini.add(g.get(nod2));

			// pentru neorientat
			// g.get(nod1).vecini.add(g.get(nod2));
		}

		s.close();
	}

	public static void afiG(ArrayList<Nod> g) {
		for (Nod nod : g) {
			System.out.print("id " + nod.id + " timp " + nod.timp + " : ");
			for (Nod n : nod.vecini) {
				System.out.print(n.id + " ");
			}
			System.out.println();
		}
	}

	public static void sleep(int ms) {
		try {
			Thread.sleep(ms);
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}