Pagini recente » Cod sursa (job #2356549) | Cod sursa (job #1831504) | Cod sursa (job #2068429) | Cod sursa (job #87980) | Cod sursa (job #1784576)
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
const int nmax = 100010;
int n, m, x, y, topsort[nmax];
vector<int> g[nmax], gt[nmax];
vector<int> crtctc;
vector<vector<int> > ctc;
bool used[nmax];
void dfp(int node)
{
used[node] = 1;
for (int vec : g[node])
{
if (used[vec])
continue;
dfp(vec);
}
topsort[++topsort[0]] = node;
}
void dfm(int node)
{
used[node] = 0;
crtctc.push_back(node);
for (int vec : gt[node])
{
if (!used[vec])
continue;
dfm(vec);
}
}
int main()
{
freopen("in", "r", stdin);
scanf("%i %i", &n, &m);
for (int i = 1; i <= m; ++ i)
{
scanf("%i %i", &x, &y);
g[x].push_back(y);
gt[y].push_back(x);
}
for (int i = 1; i <= n; ++ i)
if (!used[i])
dfp(i);
reverse(topsort + 1, topsort + topsort[0] + 1);
for (int i = 1; i <= n; ++ i)
if (used[topsort[i]])
{
crtctc.clear();
dfm(topsort[i]);
ctc.push_back(crtctc);
}
printf("%i\n", ctc.size());
for (int i = 0; i < ctc.size(); ++ i, printf("\n"))
for (int j = 0; j < ctc[i].size(); ++ j)
printf("%i ", ctc[i][j]);
}