Cod sursa(job #1705204)

Utilizator TheDeathEne Bogdan Adrian TheDeath Data 20 mai 2016 01:28:55
Problema Sortare topologica Scor 70
Compilator java Status done
Runda Arhiva educationala Marime 4.15 kb
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

class Graph {

	public int numNodes;// numarul de noduri din graf
	public int muchii;// numarul de portale
	public int[] indegree;

	public List<List<Integer>> edges;// definim muchiile ca lista de lista unde
										// indicele primei liste este
	// nodul de plecare si indicele celui de-al doilea este nodul spre care se
	// duce
	// initializam lista si adaugam un element pentru ca indicii trebuie sa
	// coincida cu ID nodului

	public Graph() {
		edges = new ArrayList<>();
		edges.add(new ArrayList<Integer>());
	}

	// functie ce insereaza cate un arraylist pentru fiecare nod
	public void insertNode() {
		edges.add(new ArrayList<Integer>());

	}

	// functie ce ne insereaza muchia efectiv
	public void insertEdge(int fromNodeIdx, int toNodeIdx) {
		edges.get(fromNodeIdx).add(toNodeIdx);
	}

	public void insertInEdge(int fromNodeIdx, int toNodeIdx) {

	}

	// functie pentru citirea fisierului de intrare si parsarea acestuia in
	// variabilele si listele create
	public void readData(BufferedReader input) throws IOException {
		StringTokenizer tokenizer;
		String read = input.readLine();
		tokenizer = new StringTokenizer(read, " ");
		numNodes = Integer.parseInt(tokenizer.nextToken());
		muchii = Integer.parseInt(tokenizer.nextToken());
		indegree = new int[numNodes + 1];
		// inseram cate o lista pentru fiecare nod
		for (int i = 1; i <= numNodes; i++) {
			insertNode();

		}
		int count = 0;
		for (int edgeIdx = 0; edgeIdx < muchii; edgeIdx++) {

			read = input.readLine();
			tokenizer = new StringTokenizer(read, " ");
			int node1 = Integer.parseInt(tokenizer.nextToken());

			int node2 = Integer.parseInt(tokenizer.nextToken());

			// muchia o inseram in ambele directii deoarece la inceput este
			// neorientat
			insertEdge(node1, node2);
			// System.out.println(map.get(node2));
			indegree[node2]++;

		}

	}

	@Override // functie de test pentru a vedea graful
	public String toString() {

		StringBuilder sb = new StringBuilder("Print Graph:\n");

		for (int n = 1; n <= numNodes; n++) {
			sb.append("OutEdges for " + n + " -> ");

			for (Integer edge : edges.get(n)) {
				sb.append(edge);
				sb.append(" | ");
			}

			sb.append("\n");
		}
		sb.append("\n");

		return sb.toString();

	}
}

class Kahn {
	int[] indegree;
	int nr;
	public List<List<Integer>> edges;
	BufferedWriter output;
	public Kahn(BufferedWriter output){
		this.output = output;
	}
	public void TopSort(Graph g) throws IOException {
		nr = g.numNodes;
		indegree = g.indegree;
		edges = g.edges;
		//System.out.println(nr);
		List<Integer> finish = new ArrayList<Integer>();
		Stack<Integer> S = new Stack<Integer>();
		for (int i = 0; i < nr; i++) {
			if (indegree[i] == 0) {
				S.push(i);
			}
		}
		
		while(!S.isEmpty()){
			int u = S.pop();
			finish.add(u);
			for(Integer a : edges.get(u)){
				indegree[a]--;
				if(indegree[a]<=0){
					S.push(a);
				}
				
			}
			
		}
		
		
		for(int i = 0; i<finish.size()-1;i++)
			if(i<finish.size()-2)
				output.write(finish.get(i)+ " ");
			else
				output.write(finish.get(i).toString());
				

	}

}

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader input = new BufferedReader(new FileReader("sortaret.in"));// deschidem
		BufferedWriter output = new BufferedWriter(new FileWriter("sortaret.out"));																			// fisierul
																					// pentru
																					// citire

		Graph g = new Graph();// creem un obiect graph
		g.readData(input);// citim datele cu functia readdata
		// System.out.println(g);
		Kahn kahn = new Kahn(output);// creem un obiect dfs
		kahn.TopSort(g);
		// scriem in fisierul de iesire rezultatul functiei doDfs
		// output.write(dfs.doDFS()+"\n");
		// inchidem fisierele de intrare si de iesire
		input.close();
		output.close();

	}
}