Pagini recente » Cod sursa (job #2204864) | Cod sursa (job #2054763) | Cod sursa (job #555583) | Cod sursa (job #1508747) | Cod sursa (job #2586856)
//tlim1969_L1_4.java
//Tempfli Levente, 514/1
//L1,F4
package Main;
import java.io.*;
import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;
import static java.lang.Integer.min;
public class Main {
public static void main(String[] args) throws IOException {
Graph graph = new Graph("ctc.in");
ArrayList<LinkedList<Integer>> scc_components = graph.scc_tarjan();
FileWriter fileWriter = new FileWriter("ctc.out");
PrintWriter printWriter = new PrintWriter(fileWriter);
printWriter.print(scc_components.size());
for (LinkedList<Integer> ll : scc_components) {
printWriter.print("\n");
for (Integer e : ll) {
printWriter.print(e);
printWriter.print(" ");
}
}
printWriter.close();
fileWriter.close();
}
}
class Graph {
//Konstruktor-Beolvasas
public Graph(String filename) throws FileNotFoundException {
File file = new File(filename);
Scanner scanner = new Scanner(file);
int n, m;
n = scanner.nextInt();
m = scanner.nextInt();
adj_list = new ArrayList<LinkedList<Integer>>();
for (int i = 0; i <= n; i++) {
adj_list.add(new LinkedList<Integer>());
}
seen = new ArrayList<Integer>(Collections.nCopies(n + 1, 0));
low = new ArrayList<Integer>(Collections.nCopies(n + 1, 0));
id = new ArrayList<Integer>(Collections.nCopies(n + 1, 0));
stack = new Stack<Integer>();
int f, g;
for (int i = 0; i < m; i++) {
f = scanner.nextInt();
g = scanner.nextInt();
adj_list.get(f).add(g);
}
}
//Komponensek kiszamitasa
public ArrayList<LinkedList<Integer>> scc_tarjan() {
ArrayList<LinkedList<Integer>> components = new ArrayList<LinkedList<Integer>>();
for (int i = 1; i < adj_list.size(); i++) {
seen.set(i, 0);
}
stack.clear();
for (int i = 1; i < adj_list.size(); i++) {
if (seen.get(i) == 0) {
DFSR_tarjan(components, i, 0);
}
}
return components;
}
//Melysegi bejaras es tarjanozas
private int DFSR_tarjan(ArrayList<LinkedList<Integer>> components, int i, int previd) {
if (seen.get(i) == 2) return Integer.MAX_VALUE;
if (seen.get(i) == 1) return low.get(i);
id.set(i, previd + 1);
stack.push(i);
seen.set(i, 1);
low.set(i, id.get(i));
Iterator<Integer> it = adj_list.get(i).listIterator();
while (it.hasNext()) {
low.set(i,min(DFSR_tarjan(components, it.next(), id.get(i)), low.get(i)));
}
if (low.get(i) == id.get(i)) {
components.add(new LinkedList<>());
do {
components.get(components.size() - 1).push(stack.peek());
seen.set(stack.peek(), 2);
} while (stack.pop() != i);
}
return low.get(i);
}
private ArrayList<LinkedList<Integer>> adj_list;
private ArrayList<Integer> seen;
private ArrayList<Integer> low;
private Stack<Integer> stack;
private ArrayList<Integer> id;
}