Pagini recente » Cod sursa (job #614181) | Cod sursa (job #2738338) | Cod sursa (job #3174390) | Cod sursa (job #1732460) | Cod sursa (job #938003)
Cod sursa(job #938003)
#include <fstream>
#include <bitset>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
using namespace std;
ifstream fi ("ctc.in");
ofstream fo ("ctc.out");
const int dim = 100005;
int N, M, NC, top[dim];
vector <int> V[dim], VT[dim], C[dim];
bitset <dim> viz;
void cit ()
{
fi >> N >> M;
for (int i = 1, a, b; i <= M; i++)
{
fi >> a >> b;
V[a].push_back (b);
VT[b].push_back (a);
}
}
void dfs (int n)
{
viz[n] = 1;
for (int i = 0; i < V[n].size(); i++)
if (viz[V[n][i]] == 0)
dfs (V[n][i]);
top[++top[0]] = n;
}
void dfst (int n)
{
viz[n] = 0;
C[NC].push_back (n);
for (int i = 0; i < VT[n].size(); i++)
if (viz[VT[n][i]])
dfst (VT[n][i]);
}
void rez ()
{
for (int i = 1; i <= N; i++)
if (viz[i] == 0)
dfs (i);
for (int i = N; i >= 1; i--)
if (viz[top[i]])
{
NC ++;
dfst (top[i]);
}
}
void afi ()
{
fo << NC << '\n';
for (int i = 1, j; i <= NC; i++)
{
for (j = 0; j < C[i].size(); j++)
fo << C[i][j] << ' ';
fo << '\n';
}
}
int main ()
{
cit ();
rez ();
afi ();
return 0;
}