Pagini recente » Cod sursa (job #824857) | Cod sursa (job #1395941) | Cod sursa (job #766691) | Cod sursa (job #1931152) | Cod sursa (job #384123)
Cod sursa(job #384123)
#include <stdio.h>
#include <vector>
using namespace std;
#define NMAX 100020
#define FOR(i, v) for(vector<int>::iterator i = v.begin(); i != v.end(); ++i)
vector <int> G[NMAX], Gt[NMAX], S[NMAX];
int t[NMAX], T[NMAX];
bool ok[NMAX];
int n , m, c;
void dfs1(int x){
if(ok[x]) return;
ok[x] = true;
t[++t[0]] = x;
FOR(i, G[x])
dfs1(*i);
}
void dfs2(int x){
if(ok[x]) return;
ok[x] = true;
T[x] = c;
FOR(i, Gt[x])
dfs2(*i);
}
void afisare(){
printf("%d\n", c);
for(int i = 1; i <= n; ++i)
S[T[i]].push_back(i);
for(int i = 1; i <= c; ++i){
FOR(it, S[i])
printf("%d ", *it);
printf("\n");
}
}
int main(){
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++i){
int x, y;
scanf("%d%d", &x, &y);
G[x].push_back(y);
Gt[y].push_back(x);
}
for(int i = 1; i <= n; ++i)
//if(!ok[i])
dfs1(i);
//int c = 0;
memset(ok, 0, sizeof(ok));
for(int i = 1; i <= t[0]; ++i)
if(!T[t[i]]){
c++;
dfs2(t[i]);
}
afisare();
}