Pagini recente » Cod sursa (job #3230608) | Cod sursa (job #1378606) | Cod sursa (job #1662996) | Cod sursa (job #1353723) | Cod sursa (job #1836454)
import java.util.*;
import java.io.*;
import java.lang.*;
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 = new Main().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();
}
List<Integer>[] graph;
boolean[] visited;
Stack<Integer> stack;
int time;
int[] lowlink;
List<List<Integer>> components;
public List<List<Integer>> scc(List<Integer>[] graph) {
int n = graph.length;
this.graph = graph;
visited = new boolean[n];
stack = new Stack<>();
time = 0;
lowlink = new int[n];
components = new ArrayList<>();
for (int u = 0; u < n; u++)
if (!visited[u])
dfs(u);
return components;
}
void dfs(int u) {
lowlink[u] = time++;
visited[u] = true;
stack.add(u);
boolean isComponentRoot = true;
for (int v : graph[u]) {
if (!visited[v])
dfs(v);
if (lowlink[u] > lowlink[v]) {
lowlink[u] = lowlink[v];
isComponentRoot = false;
}
}
if (isComponentRoot) {
List<Integer> component = new ArrayList<>();
while (true) {
int x = stack.pop();
component.add(x);
lowlink[x] = Integer.MAX_VALUE;
if (x == u)
break;
}
components.add(component);
}
}
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());
}
}
}