Mai intai trebuie sa te autentifici.
Cod sursa(job #1705572)
Utilizator | Data | 20 mai 2016 19:46:07 | |
---|---|---|---|
Problema | Sortare topologica | Scor | 0 |
Compilator | java | Status | done |
Runda | Arhiva educationala | Marime | 2.61 kb |
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Random;
import java.util.Stack;
class Pair {
int node1;
int node2;
public Pair(int node1, int node2) {
this.node1 = node1;
this.node2 = node2;
}
}
public class Main {
private static int N, M, node1, node2;
private static ArrayList<ArrayList<Integer>> adjList;
private static int dTime[];
private static int fTime[];
private static int inVertices[];
private static ArrayList<Integer> solutionList = new ArrayList<Integer>();
private static Stack<Integer> stack = new Stack<Integer>();
private static void readData() throws IOException {
BufferedReader bf = new BufferedReader(new FileReader("sortare.in"));
String tmp[] = bf.readLine().split(" ");
N = Integer.parseInt(tmp[0]);
M = Integer.parseInt(tmp[1]);
adjList = new ArrayList<ArrayList<Integer>>(N + 1);
//initializare vector timp de descoperire
dTime = new int[N + 1];
//initializare vector timp de finalizare
fTime = new int[N + 1];
//initializare vector pentru in-muchii
inVertices = new int[N + 1];
for(int i = 1; i <= N; i ++) {
adjList.add(new ArrayList<Integer>(N));
fTime[i] = 0;
dTime[i] = 0;
inVertices[i] = 0;
}
//adaugam ceva pe pozitia 1 in lista de adiacenta
adjList.add(0, null);
for(int i = 0; i < M; i ++) {
tmp = bf.readLine().split(" ");
node1 = Integer.parseInt(tmp[0]);
node2 = Integer.parseInt(tmp[1]);
Pair p = new Pair(node1, node2);
adjList.get(p.node1).add(p.node2);
inVertices[node2] ++;
}
}
private static ArrayList<Integer> topSort() {
//pentru fiecare nod
for(int i = 1; i <= N; i ++) {
//daca nodul respectiv nu are in-muchii
if(inVertices[i] == 0) {
stack.add(i);
}
}
while(!stack.isEmpty()) {
int element = stack.pop();
solutionList.add(element);
//pentru fiecare vecin al nodului scos din stiva
for(int j = 0; j < adjList.get(element).size(); j ++) {
int number = adjList.get(element).get(j);
inVertices[number] --;
adjList.get(element).remove(j);
if(inVertices[number] == 0) {
stack.add(number);
}
j --;
}
}
//verificam daca graful mai are muchii
for(int i = 1; i <= N; i ++) {
if(inVertices[i] > 0) {
System.out.println("Eroare, graful este ciclic");
break;
}
}
return solutionList;
}
public static void main(String[] args) throws IOException {
readData();
topSort();
PrintWriter pw = new PrintWriter("sortare.out");
pw.println(solutionList);
pw.close();
}
}