Pagini recente » Cod sursa (job #1316806) | Cod sursa (job #1400475) | Cod sursa (job #2329708) | Cod sursa (job #2441068) | Cod sursa (job #1430605)
import java.io.*;
import java.util.*;
/**
* Created by intern on 5/8/15.
*/
public class Main {
private List<Integer>[] neighbours;
private PrintWriter printWriter;
private static String outTxt = "sortaret.out";
public Main(List<Integer>[] neighbours)
{
try {
printWriter = new PrintWriter(outTxt, "UTF-8");
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (UnsupportedEncodingException e) {
e.printStackTrace();
}
this.neighbours = neighbours;
}
public static void main(String[] args) throws IOException {
FileReader in = null;
String line = null;
int n = 0;
int m = 0;
try {
in = new FileReader("sortaret.in");
} catch (FileNotFoundException e) {
e.printStackTrace();
}
BufferedReader br = new BufferedReader(in);
line = br.readLine();
Scanner scanner = new Scanner(line);
n = scanner.nextInt();
m = scanner.nextInt();
List<Integer>[] neighbours = new List[n];
for (int i = 0;i < n;i++)
{
neighbours[i] = new ArrayList<>();
}
int edgeFrom,edgeTo;
for (int i = 0;i < m; i++)
{
line = br.readLine();
scanner = new Scanner(line);
edgeFrom = scanner.nextInt();
edgeTo = scanner.nextInt();
neighbours[edgeFrom - 1].add(edgeTo - 1);
}
br.close();
Main topoSort = new Main(neighbours);
topoSort.dfs();
}
public void dfs()
{
int n = neighbours.length;
boolean[] visited = new boolean[n];
Deque<Integer> integers = new LinkedList<>();
for (int i = 0;i < n;i++)
{
if (!visited[i]) dfsComponent(i,visited,integers);
}
for (Integer i : integers)
printWriter.print(i + 1 + " ");
printWriter.close();
}
private void dfsComponent(int i,boolean[] visited,Deque<Integer> integers) {
visited[i] = true;
for (Integer neighbour : neighbours[i])
{
if(!visited[neighbour])
{
dfsComponent(neighbour,visited,integers);
}
}
integers.addFirst(i);
}
}