Pagini recente » Cod sursa (job #2509946) | Cod sursa (job #2638769) | Cod sursa (job #2736866) | Cod sursa (job #2933546) | Cod sursa (job #1352457)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define MAXN 100050
using namespace std;
int n, m, nm[MAXN], viz[MAXN], nq;
vector<int> v[MAXN];
vector<int> trV[MAXN];
vector<int> compo[MAXN];
vector<int> post;
void citire()
{
int x, y;
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++)
{
scanf("%d %d", &x, &y);
v[x].push_back(y);
trV[y].push_back(x);
}
}
void rdfs(int x)
{
if (nm[x]) return;
compo[nq].push_back(x);
nm[x] = 1;
for (int i = 0; i < trV[x].size(); i++)
rdfs(trV[x][i]);
}
void postOrd(int x)
{
if (viz[x]) return;
viz[x] = 1;
for (int i = 0; i < v[x].size(); i++)
postOrd(v[x][i]);
post.push_back(x);
}
void solve()
{
for (int i = 1; i <= n; i++)
if (!viz[i])
postOrd(i);
for (int i = post.size()-1; i >= 0; i--)
if (!nm[post[i]])
{
rdfs(post[i]);
nq++;
}
}
void afisare()
{
printf("%d\n", nq);
for (int i = 0; i < nq; i++)
{
for (int j = 0; j < compo[i].size(); j++)
printf("%d ", compo[i][j]);
printf("\n");
}
// printf("\n\n");
//for (int i = 0; i < post.size(); i++)
// printf("%d ", post[i]);
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
citire();
solve();
afisare();
return 0;
}