Pagini recente » Cod sursa (job #2719196) | Cod sursa (job #2480643) | Cod sursa (job #2227657) | Cod sursa (job #1983539) | Cod sursa (job #1836449)
import java.util.*;
import java.io.*;
import java.lang.*;
import java.util.stream.Stream;
public class Main {
public static void main(String[] args) throws FileNotFoundException {
InputReader in = new InputReader(new FileInputStream("ctc.in"));
PrintWriter out = new PrintWriter(new FileOutputStream("ctc.out"));
int n = in.nextInt(), m = in.nextInt();
List<Integer>[] graph = new List[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < m; i++) {
int x = in.nextInt() - 1;
int y = in.nextInt() - 1;
graph[x].add(y);
}
List<List<Integer>> stronglyConnectedComponents = scc(graph);
out.println(stronglyConnectedComponents.size());
for (List<Integer> component: stronglyConnectedComponents) {
for (Integer x: component) {
out.print(x + 1);
out.print(' ');
}
out.print('\n');
}
out.close();
}
public static List<List<Integer>> scc(List<Integer>[] graph) {
int n = graph.length;
int[] stack = new int[n];
int st = 0;
int[] stack_cur = new int[n];
int[] stack_pos = new int[n];
int[] stack_prev = new int[n];
int[] index = new int[n];
Arrays.fill(index, -1);
int[] lowlink = new int[n];
int time = 0;
List<List<Integer>> components = new ArrayList<>();
for (int u = 0; u < n; u++) {
if (index[u] == -1) {
int top = 0;
stack_cur[top] = u;
stack_pos[top] = 0;
stack_prev[top] = -1;
while (top >= 0) {
int cur = stack_cur[top];
int pos = stack_pos[top];
if (index[cur] == -1) {
index[cur] = time;
lowlink[cur] = time;
++time;
stack[st++] = cur;
}
if (pos < graph[cur].size()) {
int v = graph[cur].get(pos);
++stack_pos[top];
if (index[v] == -1) {
++top;
stack_cur[top] = v;
stack_pos[top] = 0;
stack_prev[top] = cur;
} else {
lowlink[cur] = Math.min(lowlink[cur], lowlink[v]);
}
} else {
int prev = stack_prev[top];
if (prev != -1) {
lowlink[prev] = Math.min(lowlink[prev], lowlink[cur]);
}
if (lowlink[cur] == index[cur]) {
List<Integer> component = new ArrayList<>();
while (true) {
int v = stack[--st];
lowlink[v] = Integer.MAX_VALUE;
component.add(v);
if (v == cur)
break;
}
components.add(component);
}
--top;
}
}
}
}
return components;
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}