Pagini recente » Cod sursa (job #3294538) | Cod sursa (job #1366050) | Cod sursa (job #1230676) | pauloji_2010 | Cod sursa (job #1705849)
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) {
}
}
}
}
}