Pagini recente » Cod sursa (job #56677) | Cod sursa (job #1448846) | Cod sursa (job #2981764) | Cod sursa (job #2823932) | Cod sursa (job #1361325)
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
#define MAX_N 100000
#define MAX_M 200000
using namespace std;
int n, m;
vector<int> G[MAX_N];
vector<int> GT[MAX_N];
stack<int> S;
bool viz[MAX_N];
int nr_ctc;
vector<int> ctc[MAX_N];
void read() {
freopen("ctc.in", "r", stdin);
scanf("%d %d", &n, &m);
for(int i = 0; i < m; i++) {
int x, y;
scanf("%d %d", &x, &y);
x--; y--;
G[x].push_back(y);
GT[y].push_back(x);
}
fclose(stdin);
}
void write() {
freopen("ctc.out", "w", stdout);
printf("%d\n", nr_ctc);
for(int i = 0; i < nr_ctc; i++) {
for(int j = 0; j < ctc[i].size(); j++) {
printf("%d ", ctc[i][j] + 1);
}
printf("\n");
}
fclose(stdout);
}
void DFS(int v) {
viz[v] = true;
for(int i = 0; i < G[v].size(); i++) {
int child = G[v][i];
if(!viz[child]) {
DFS(child);
}
}
S.push(v);
}
void connect(int v, int comp) {
viz[v] = true;
ctc[comp].push_back(v);
for(int i = 0; i < GT[v].size(); i++) {
int child = GT[v][i];
if(!viz[child]) {
connect(child, comp);
}
}
}
void solve() {
for(int i = 0; i < n; i++) {
if(!viz[i]) {
DFS(i);
}
}
memset(viz, false, n);
while(!S.empty()) {
int v = S.top();
S.pop();
if(!viz[v]) {
connect(v, nr_ctc++);
}
}
}
int main() {
read();
solve();
write();
return 0;
}