Pagini recente » Cod sursa (job #968676) | Cod sursa (job #1953778) | Cod sursa (job #2437715) | Rating Danila Albert (NewGuyAlbert) | Cod sursa (job #1705207)
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;
class Graph {
public int numNodes;// numarul de noduri din graf
public int muchii;// numarul de portale
public int[] indegree;
public List<List<Integer>> edges;// definim muchiile ca lista de lista unde
// indicele primei liste este
// nodul de plecare si indicele celui de-al doilea este nodul spre care se
// duce
// initializam lista si adaugam un element pentru ca indicii trebuie sa
// coincida cu ID nodului
public Graph() {
edges = new ArrayList<>();
edges.add(new ArrayList<Integer>());
}
// functie ce insereaza cate un arraylist pentru fiecare nod
public void insertNode() {
edges.add(new ArrayList<Integer>());
}
// functie ce ne insereaza muchia efectiv
public void insertEdge(int fromNodeIdx, int toNodeIdx) {
edges.get(fromNodeIdx).add(toNodeIdx);
}
public void insertInEdge(int fromNodeIdx, int toNodeIdx) {
}
// functie pentru citirea fisierului de intrare si parsarea acestuia in
// variabilele si listele create
public void readData(BufferedReader input) throws IOException {
StringTokenizer tokenizer;
String read = input.readLine();
tokenizer = new StringTokenizer(read, " ");
numNodes = Integer.parseInt(tokenizer.nextToken());
muchii = Integer.parseInt(tokenizer.nextToken());
indegree = new int[numNodes + 1];
// inseram cate o lista pentru fiecare nod
for (int i = 1; i <= numNodes; i++) {
insertNode();
}
int count = 0;
for (int edgeIdx = 0; edgeIdx < muchii; edgeIdx++) {
read = input.readLine();
tokenizer = new StringTokenizer(read, " ");
int node1 = Integer.parseInt(tokenizer.nextToken());
int node2 = Integer.parseInt(tokenizer.nextToken());
// muchia o inseram in ambele directii deoarece la inceput este
// neorientat
insertEdge(node1, node2);
// System.out.println(map.get(node2));
indegree[node2]++;
}
}
@Override // functie de test pentru a vedea graful
public String toString() {
StringBuilder sb = new StringBuilder("Print Graph:\n");
for (int n = 1; n <= numNodes; n++) {
sb.append("OutEdges for " + n + " -> ");
for (Integer edge : edges.get(n)) {
sb.append(edge);
sb.append(" | ");
}
sb.append("\n");
}
sb.append("\n");
return sb.toString();
}
}
class Kahn {
int[] indegree;
int nr;
public List<List<Integer>> edges;
BufferedWriter output;
public Kahn(BufferedWriter output) {
this.output = output;
}
public void TopSort(Graph g) throws IOException {
int visited = 0;
nr = g.numNodes;
indegree = g.indegree;
edges = g.edges;
// System.out.println(nr);
List<Integer> finish = new ArrayList<Integer>();
Stack<Integer> S = new Stack<Integer>();
for (int i = 0; i < nr; i++) {
if (indegree[i] == 0) {
S.push(i);
}
}
while (!S.isEmpty()) {
int u = S.pop();
finish.add(u);
visited++;
for (Integer a : edges.get(u)) {
indegree[a]--;
if (indegree[a] == 0) {
S.push(a);
}
}
}
visited--;
if (visited != nr){
output.write("CICLU\n");
}
else
for (int i = 0; i < finish.size() - 1; i++)
if (i < finish.size() - 2)
output.write(finish.get(i) + " ");
else
output.write(finish.get(i).toString());
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader input = new BufferedReader(new FileReader("sortaret.in"));// deschidem
BufferedWriter output = new BufferedWriter(new FileWriter("sortaret.out")); // fisierul
// pentru
// citire
Graph g = new Graph();// creem un obiect graph
g.readData(input);// citim datele cu functia readdata
// System.out.println(g);
Kahn kahn = new Kahn(output);// creem un obiect dfs
kahn.TopSort(g);
// scriem in fisierul de iesire rezultatul functiei doDfs
// output.write(dfs.doDFS()+"\n");
// inchidem fisierele de intrare si de iesire
input.close();
output.close();
}
}