Pagini recente » Cod sursa (job #839269) | Cod sursa (job #2589783) | Cod sursa (job #1483837) | Cod sursa (job #2675142) | Cod sursa (job #1430592)
import java.io.*;
import java.util.*;
/**
* Created by intern on 5/8/15.
*/
public class TopoSort {
private List<Integer>[] neighbours;
private PrintWriter printWriter;
private static String outTxt = "sortaret.out";
public TopoSort(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);
}
for (int i = 0;i< n;i++)
System.out.println(neighbours[i]);
br.close();
TopoSort topoSort = new TopoSort(neighbours);
topoSort.dfs();
}
public void dfs()
{
int n = neighbours.length;
boolean[] visited = new boolean[n];
for (int i = 0;i<n;i++)
visited[i] = false;
Deque<Integer> integers = new ArrayDeque<>();
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> queue) {
visited[i] = true;
for (Integer neighbour : neighbours[i])
{
if(!visited[neighbour])
{
dfsComponent(neighbour,visited,queue);
}
}
queue.addFirst(i);
}
}