Pagini recente » Cod sursa (job #2890466) | Cod sursa (job #1143441) | Cod sursa (job #1448628) | Cod sursa (job #2640319) | Cod sursa (job #3269263)
import java.io.*;
import java.util.*;
public class Main {
public static class MyScanner implements Closeable {
BufferedReader br;
StringTokenizer st;
public MyScanner(String file) throws FileNotFoundException {
br = new BufferedReader(new InputStreamReader(new FileInputStream(file)), 1 << 16);
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine(){
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
@Override
public void close() throws IOException {
br.close();
}
}
public static class DirectedGraph {
private List<Integer>[] adjList;
private int N;
public DirectedGraph(int N) {
this.N = N;
adjList = (List<Integer>[]) new List[N+1];
}
public void addEdge(int u, int v) {
if (adjList[u] == null) {
adjList[u] = new ArrayList<>();
}
adjList[u].add(v);
}
public List<Integer> neighbors(int u) {
if (adjList[u] == null) {
return Collections.emptyList();
} else {
return adjList[u];
}
}
public int size() {
return N;
}
}
public static int time = 0;
public static Stack<Integer> stack = new Stack<>();
public static boolean[] onStack;
public static boolean[] visited;
public static int[] discovery;
public static int[] lowLink;
public static List<List<Integer>> scc = new ArrayList<>();
public static void dfsTarjanVisit(int u, DirectedGraph g) {
visited[u] = true;
time++;
discovery[u] = time;
lowLink[u] = time;
stack.push(u);
onStack[u] = true;
for (int v : g.neighbors(u)) {
if (!visited[v]) {
dfsTarjanVisit(v, g);
lowLink[u] = Math.min(lowLink[u], lowLink[v]);
} else if (onStack[v]) {
lowLink[u] = Math.min(lowLink[u], discovery[v]);
}
}
if (lowLink[u] == discovery[u]) { // this root belongs to a scc
List<Integer> newScc = new ArrayList<>();
newScc.add(u);
while (stack.peek() != u) {
int fromStack = stack.pop();
newScc.add(fromStack);
onStack[fromStack] = false;
}
stack.pop();
onStack[u] = false;
scc.add(newScc);
}
}
public static void dfsTarjan(DirectedGraph g) {
for (int i = 1; i <= g.size(); i++) {
if (!visited[i]) {
dfsTarjanVisit(i, g);
}
}
}
public static void main(String[] args) throws IOException {
try(MyScanner scanner = new MyScanner("ctc.in");
PrintWriter fw = new PrintWriter(new FileOutputStream("ctc.out"))) {
int N = scanner.nextInt();
int M = scanner.nextInt();
DirectedGraph g = new DirectedGraph(N);
visited = new boolean[N+1];
onStack = new boolean[N+1];
discovery = new int[N+1];
lowLink = new int[N+1];
for (int i = 1; i <= M; i++) {
g.addEdge(scanner.nextInt(), scanner.nextInt());
}
dfsTarjan(g);
fw.println(scc.size());
for (List<Integer> aScc : scc) {
for (Integer comp : aScc) {
fw.print(comp + " ");
}
fw.println();
}
}
}
}