Pagini recente » Cod sursa (job #2659106) | Cod sursa (job #2411056) | Cod sursa (job #3222009) | Cod sursa (job #739605) | Cod sursa (job #2203332)
import java.io.*;
import java.util.*;
public class Main {
public static final int NMAX = 1000005;
public static final int WHITE = 1;
public static final int GRAY = 2;
public static final int BLACK = 3;
int N;
int M;
int c[];
int k = 0;
Stack<Integer> S = new Stack<Integer>();
@SuppressWarnings("unchecked")
ArrayList<Integer> adj[] = new ArrayList[NMAX];
@SuppressWarnings("unchecked")
ArrayList<Integer> adjT[] = new ArrayList[NMAX];
@SuppressWarnings("unchecked")
TreeSet<Integer> comps[] = new TreeSet[NMAX];
public void readInput() {
Scanner sc;
try {
sc = new Scanner(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 <= N; i++)
adjT[i] = new ArrayList<>();
for (int i = 1; i <= M; i++) {
int x, y;
x = sc.nextInt();
y = sc.nextInt();
adj[x].add(y);
adjT[y].add(x);
}
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
public void explore(int u) {
c[u] = GRAY;
for (int v : adj[u]) {
if (c[v] == WHITE) {
explore(v);
}
}
c[u] = BLACK;
S.push(u);
}
public void exploreT(int u) {
c[u] = GRAY;
comps[k].add(u);
for (int v : adjT[u]) {
if (c[v] == WHITE) {
exploreT(v);
}
}
c[u] = BLACK;
}
public void solve() {
try {
PrintWriter out = new PrintWriter("ctc.out");
c = new int[N + 1];
for (int u = 1; u <= N; u++) {
c[u] = WHITE;
}
for (int u = 1; u <= N; u++) {
if (c[u] == WHITE) {
explore(u);
}
}
for (int u = 1; u <= N; u++) {
c[u] = WHITE;
}
while (!S.isEmpty()) {
int u = S.pop();
if (c[u] == WHITE) {
k++;
comps[k] = new TreeSet<Integer>();
exploreT(u);
}
}
out.println(k);
for (int i = 1; i <= k; i++) {
for (int u : comps[i]) {
out.print(u + " ");
}
out.println();
}
out.close();
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
public static void main(String[] args) {
Main ctc = new Main();
ctc.readInput();
ctc.solve();
}
}