Cod sursa(job #1705570)

Utilizator Osman_RuxandraOsman Maria - Ruxandra Osman_Ruxandra Data 20 mai 2016 19:45:17
Problema Sortare topologica Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.48 kb
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Random;
import java.util.Stack;

public class Main {

	private static int N, M, node1, node2;
	private static ArrayList<ArrayList<Integer>> adjList;
	private static int dTime[];
	private static int fTime[];
	private static int inVertices[];
	private static ArrayList<Integer> solutionList = new ArrayList<Integer>();
	private static Stack<Integer> stack = new Stack<Integer>();
	
	private static void readData() throws IOException {
		BufferedReader bf = new BufferedReader(new FileReader("sortare.in"));
		String tmp[] = bf.readLine().split(" ");
        N = Integer.parseInt(tmp[0]);
        M = Integer.parseInt(tmp[1]);
		adjList = new ArrayList<ArrayList<Integer>>(N + 1);
		//initializare vector timp de descoperire
		dTime = new int[N + 1];
		//initializare vector timp de finalizare
		fTime = new int[N + 1];
		//initializare vector pentru in-muchii
		inVertices = new int[N + 1];

		for(int i = 1; i <= N; i ++) {
			adjList.add(new ArrayList<Integer>(N));
			fTime[i] = 0;
			dTime[i] = 0;
			inVertices[i] = 0;
		}
		
		//adaugam ceva pe pozitia 1 in lista de adiacenta
		adjList.add(0, null);
		for(int i = 0; i < M; i ++) {
			tmp = bf.readLine().split(" ");
	        node1 = Integer.parseInt(tmp[0]);
	        node2 = Integer.parseInt(tmp[1]);
			Pair p = new Pair(node1, node2);
			adjList.get(p.node1).add(p.node2);
			inVertices[node2] ++;
		}
	}
	
	private static ArrayList<Integer> topSort() {
		//pentru fiecare nod
		for(int i = 1; i <= N; i ++) {
			//daca nodul respectiv nu are in-muchii
			if(inVertices[i] == 0) {
				stack.add(i);
			}
		}
		while(!stack.isEmpty()) {
			int element = stack.pop();
			solutionList.add(element);
			//pentru fiecare vecin al nodului scos din stiva
			
			for(int j = 0; j < adjList.get(element).size(); j ++) {
				int number = adjList.get(element).get(j);
				inVertices[number] --;
				adjList.get(element).remove(j);
				if(inVertices[number] == 0) {
					stack.add(number);
				}
				j --;
			}
		}
		
		//verificam daca graful mai are muchii
		for(int i = 1; i <= N; i ++) {
			if(inVertices[i] > 0) {
				System.out.println("Eroare, graful este ciclic");
				break;
			}
		}
		return solutionList; 
	}
	
	public static void main(String[] args) throws IOException {
		readData();
		topSort();
		PrintWriter pw = new PrintWriter("sortare.out");
		pw.println(solutionList);
		pw.close();
	}
}