Pagini recente » Cod sursa (job #1885874) | Cod sursa (job #1031858) | Cod sursa (job #2393089) | Cod sursa (job #898543) | Cod sursa (job #1703553)
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.logging.Level;
import java.util.logging.Logger;
class MyScanner {
BufferedReader br;
StringTokenizer st;
public MyScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
public MyScanner(String name) throws FileNotFoundException {
InputStream input = new FileInputStream(name);
br = new BufferedReader(new InputStreamReader(input));
}
public String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
public String nextLine(){
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
class Graph {
int nodes;
ArrayList<ArrayList<Integer>> adjList;
public Graph(int N) {
nodes = N;
adjList = new ArrayList<ArrayList<Integer>>();
for(int i = 0; i <= nodes; i++) {
adjList.add(i, new ArrayList<Integer>());
}
}
public void addEdge(int src, int dest) {
adjList.get(src).add(dest);
}
public void readData(MyScanner sc, int nrEdges) {
int src, dest;
for(int i = 0; i < nrEdges; i++) {
src = sc.nextInt();
dest = sc.nextInt();
this.addEdge(src, dest);
}
}
}
public class Prob1 {
public static int M;
public static int N;
public static int[][] finTime;
public static boolean[] grey;
public static boolean[] black;
public static int time;
public static int counter;
public static void topologicalSort(Graph g) {
for(int i = 1; i <= N; i++) {
if(!black[i]) {
visit(g, i);
}
}
}
public static void visit(Graph g, int root) {
time++;
grey[root] = true;
for(int i = 0; i < g.adjList.get(root).size(); i++) {
int v = g.adjList.get(root).get(i);
if((!grey[v]) && (!black[v])) {
visit(g, v);
}
}
grey[root] = false;
black[root] = true;
finTime[0][counter] = root;
finTime[1][counter] = time++;
counter++;
}
public static void main(String[] args) throws FileNotFoundException {
MyScanner sc = new MyScanner("sortaret.in");
N = sc.nextInt();
M = sc.nextInt();
finTime = new int[2][N];
grey = new boolean[N + 1];
black = new boolean[N + 1];
Graph g = new Graph(N);
g.readData(sc, M);
time = 0;
counter = 0;
topologicalSort(g);
try {
PrintWriter out = new PrintWriter(new File("sortaret.out"));
for(int i = N - 1; i >= 1; i--) {
out.print(finTime[0][i] + " ");
}
out.println(finTime[0][0]);
out.close();
} catch (IOException ex) {
Logger.getLogger(Prob1.class.getName()).log(Level.SEVERE, null, ex);
}
}
}