Pagini recente » Cod sursa (job #3144551) | Cod sursa (job #630208) | Cod sursa (job #424956) | Cod sursa (job #911515) | Cod sursa (job #1638033)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int N = 100003;
const int M = 200003;
int nr1, nr2, nr3, n, m, nc, c[N], nrc;
int lst1[N], vf1[M], urm1[M];
int lst2[N], vf2[M], urm2[M];
bool viz1[N], viz2[N], ok;
int lst3[N], vf3[M], urm3[M];
void adauga1( int x, int y )
{
nr1++;
vf1[nr1] = y;
urm1[nr1] = lst1[x];
lst1[x] = nr1;
}
void adauga2( int x, int y )
{
nr2++;
vf2[nr2] = y;
urm2[nr2] = lst2[x];
lst2[x] = nr2;
}
void adauga3( int x, int y )
{
nr3++;
vf3[nr3] = y;
urm3[nr3] = lst3[x];
lst3[x] = nr3;
}
void dfs1( int x )
{
int y, p;
viz1[x] = true;
p = lst1[x];
while( p != 0 )
{
y = vf1[p];
if ( viz1[y] == false )
{
//viz1[y] = true;
dfs1(y);
}
p = urm1[p];
}
c[++nc] = x;
}
void dfs2( int x )
{
int y, p;
p = lst2[x];
viz2[x] = true;
while( p != 0 )
{
y = vf2[p];
if ( viz2[y] == false )
{
dfs2(y);
}
p = urm2[p];
}
adauga3(nrc, x);
//out << x<<' ';
}
void afisare( int x )
{
int p = lst3[x], y;
while( p != 0 )
{
out << vf3[p]<<' ';
p = urm3[p];
}
out <<'\n';
}
int main()
{
int i, x, y;
in >> n >> m;
for ( i = 1; i <= m; i++ )
{
in >> x >> y;
adauga1(x, y);
adauga2(y, x);
}
for ( i = 1; i <= n; i++ )
if ( viz1[i] == false )
{
dfs1(i);
}
for ( i = nc; i >= 1; i-- )
{
if ( viz2[ c[i] ] == false )
{
nrc++;
dfs2(c[i]);
}
}
out << nrc<<'\n';
for ( i = 1; i <= nrc; i++ )
{
afisare(i);
}
return 0;
}