Pagini recente » Cod sursa (job #1115064) | Cod sursa (job #2693640) | Cod sursa (job #2753089) | Cod sursa (job #1574229) | Cod sursa (job #3125969)
import java.util.Scanner;
import java.util.Stack;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.ArrayList;
public class Test {
static class Task {
public ArrayList<Integer> parent = new ArrayList<>();
public ArrayList<Integer> low_link = new ArrayList<>();
public ArrayList<Integer> found = new ArrayList<>();
public Stack<Integer> stack = new Stack<>();
public Integer time;
// numarul maxim de noduri
public static final int NMAX = (int) 1e5 + 5; // 10^5 + 5 = 100.005
// n = numar de noduri, m = numar de muchii/arce
int n, m;
// adj[node] = lista de adiacenta a nodului node
// exemplu: daca adj[node] = {..., neigh, ...} => exista arcul (node, neigh)
@SuppressWarnings("unchecked")
public ArrayList<Integer> adj[] = new ArrayList[NMAX + 1];
public void solve() {
readInput();
writeOutput(getResult());
}
private void readInput() {
try {
Scanner sc = new Scanner(new BufferedReader(new FileReader("ctc.in")));
n = sc.nextInt();
m = sc.nextInt();
for (int i = 1; i <= n; i++) {
adj[i] = new ArrayList<>();
}
for (int i = 1; i <= m; i++) {
int x, y;
x = sc.nextInt();
y = sc.nextInt();
adj[x].add(y); // arc (x, y)
}
sc.close();
} catch (Exception e) {
throw new RuntimeException(e);
}
}
private void writeOutput(ArrayList<ArrayList<Integer>> all_sccs) {
try {
BufferedWriter bw = new BufferedWriter(new FileWriter("ctc.out"));
StringBuilder sb = new StringBuilder();
sb.append(all_sccs.size()).append("\n");
for (ArrayList<Integer> scc : all_sccs) {
for (int node : scc) {
sb.append(node).append(" ");
}
sb.append("\n");
}
bw.write(sb.toString());
bw.close();
} catch (Exception e) {
throw new RuntimeException(e);
}
}
private void dfs(int node, ArrayList<ArrayList<Integer>> all_sccs) {
++time;
found.set(node, time);
low_link.set(node, found.get(node));
stack.push(node);
for (int neigh : adj[node]) {
if (parent.get(neigh) != 0) {
if (stack.contains(neigh)) {
low_link.set(node, Math.min(low_link.get(node), found.get(neigh)));
}
continue;
}
parent.set(neigh, node);
dfs(neigh, all_sccs);
low_link.set(node, Math.min(low_link.get(node), low_link.get(neigh)));
}
if (low_link.get(node) == found.get(node)) {
ArrayList<Integer> scc = new ArrayList<>();
int top;
do {
top = stack.peek();
scc.add(top);
stack.pop();
} while (top != node);
all_sccs.add(scc);
}
}
private ArrayList<ArrayList<Integer>> getResult() {
ArrayList<ArrayList<Integer>> all_sccs = new ArrayList<>();
for (int i = 1; i <= n + 1; ++i) {
parent.add(0);
low_link.add(NMAX);
found.add(NMAX);
}
time = 0;
for (int i = 1; i <= n; ++i) {
if (parent.get(i) == 0) {
parent.set(i, i);
dfs(i, all_sccs);
}
}
return all_sccs;
}
}
public static void main(String[] args) {
new Task().solve();
}
}