Pagini recente » Cod sursa (job #914528) | Cod sursa (job #3210438) | Cod sursa (job #1431260)
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;
class Nod {
public int id;
int cost = -1; // cost pana aici pentru bfs cand o muchie costa 1
int timp; // timp de atingere
public boolean viz;
public ArrayList<Nod> vecini = new ArrayList<Nod>();
// public ArrayList<Integer> costuri = new ArrayList<Integer>();
public Nod(int id) {
super();
this.id = id; // TODO ATENTI aici era +1 inainte
this.viz = false;
}
@Override
public String toString() {
return "" + this.id;
}
}
public class Main {
public static int timp, nr_ctc;
public static Stack<Nod> stack = new Stack<Nod>();
// public static ArrayList<ArrayList<Nod>> ctcuri = new ArrayList<ArrayList<Nod>>();
public static LinkedList<Nod> s = new LinkedList<Nod>();
public static void main(String[] args) throws FileNotFoundException {
PrintWriter writer = new PrintWriter(new FileOutputStream("sortaret.out"));
ArrayList<Nod> g = new ArrayList<Nod>();
readData(g);
// afiG(g);
for (Nod nod : g) {
if (nod.viz == false) {
DFS(g, nod);
}
}
while (!stack.isEmpty()) {
int u = s.pop().id + 1;
writer.write(u + " ");
}
writer.close();
}
// topsort recursiv
public static void DFS(ArrayList<Nod> g, Nod curent) {
curent.viz = true;
// parcurgem toate nodurile din graf - pentru fiecare nod incercam DFS
for (Nod vecin : curent.vecini) {
if (vecin.viz == false) {
DFS(g, vecin);
}
}
s.add(curent);
}
public static void readData(ArrayList<Nod> g) throws FileNotFoundException {
int noduri;
int muchii;
Scanner s = new Scanner(new FileInputStream("sortaret.in"));
noduri = s.nextInt();
muchii = s.nextInt();
for (int i = 0; i < noduri; i++) {
g.add(new Nod(i));
}
for (int i = 0; i < muchii; i++) {
int nod1 = s.nextInt() - 1;
int nod2 = s.nextInt() - 1;
g.get(nod1).vecini.add(g.get(nod2));
// pentru neorientat
// g.get(nod1).vecini.add(g.get(nod2));
}
s.close();
}
public static void afiG(ArrayList<Nod> g) {
for (Nod nod : g) {
System.out.print("id " + nod.id + " timp " + nod.timp + " : ");
for (Nod n : nod.vecini) {
System.out.print(n.id + " ");
}
System.out.println();
}
}
public static void sleep(int ms) {
try {
Thread.sleep(ms);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}