Cod sursa(job #1705849)

Utilizator CristianVijaeacVijaeac Cristian-Octavian CristianVijaeac Data 21 mai 2016 00:27:03
Problema Sortare topologica Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.99 kb

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;


class Main {
	
	
	static int numEdges;
	static int numNodes;
	static int source;
	static boolean[] isVisited;
	static int[] startTime;
	static int[] endTime;
	
	static class Edge{
		int start;
		int end;
		
		
		public Edge(){
			start = 0;
			end = 0;
			
		}
		
		public Edge(int start,int end){
			this.start = start;
			this.end = end;
			
		}
		
		public String toString(){
			
			return "(" + " " + this.start + " " + this.end + " )";
		}


	}


	public static void topSort(ArrayList<Edge> edge){
		
		Stack<Integer> s = new Stack<Integer>();
		ArrayList<Integer> result = new ArrayList<Integer>();
		boolean find = false;
		
		for (int i=0;i<numNodes;i++){
			find = false;
			for (int j=0;j<numEdges;j++){
				if (edge.get(j).end == i) {
					find = true;
					break;
				}
			}
			if (!find) s.push(i);
		}
		
		while(!s.isEmpty()){
			
			int n = s.pop();
			result.add(n+1);
			for (int i=0;i<numEdges;i++){
				if (edge.get(i).start == n) {
					int m = edge.get(i).end;
					edge.remove(i);
					i--;
					numEdges--;
					find = false;
					for (int j=0;j<numEdges;j++){
						if (edge.get(j).end == m) {
							find = true;
							break;
						}
					}
					if (!find) s.push(m);
					
				}
			
			}
			
		}
		
		try {
			BufferedWriter bufferedOut = new BufferedWriter( new FileWriter("sortaret.out"));
			PrintWriter out = new PrintWriter(bufferedOut);
	
		for (int i=0;i<result.size();i++)
			out.print(result.get(i));
		
		out.close();
		bufferedOut.close();
	
	} catch (IOException e) {
		e.printStackTrace();
	}
		

	
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		BufferedReader in = null;
		ArrayList<Edge> edges = new ArrayList<Edge>();		
		
		
		try {
			in = new BufferedReader(new FileReader("sortaret.in"));
			String[] aux = in.readLine().split(" ");
			numNodes = Integer.parseInt(aux[0]);
			numEdges = Integer.parseInt(aux[1]);	
			
			isVisited = new boolean[numNodes];
			startTime = new int[numNodes];
			endTime = new int[numNodes];
			
			for (int i=0;i<numNodes;i++){
				isVisited[i] = false;
				startTime = new int[numNodes];
				endTime = new int[numNodes];
			}
	
	
			for (int i = 0 ; i < numEdges ; i++){
				
				aux = in.readLine().split(" ");
				int s = Integer.parseInt(aux[0])-1;
				int e = Integer.parseInt(aux[1])-1;
				edges.add(new Edge(s,e));
			}
			
	
			
			topSort(edges);
			
		} catch (IOException e) {
			e.printStackTrace();
		
		} finally {
			if (in != null) {
		
				try {
					in.close();
				
				} catch (IOException e) {

				}
			}
		}
		
		
		
		
	
	}
}