Pagini recente » Cod sursa (job #1731130) | Cod sursa (job #1371372) | Cod sursa (job #1242648) | Cod sursa (job #495800) | Cod sursa (job #2255428)
#include <bits/stdc++.h>
#define maxn 100000
#define maxm 200000
using namespace std;
vector <int> g[2][maxn+5];
int preord[maxn+5];
int ind_prd;
bool viz[2][maxn+5];
int n_ctc;
vector <int> rez[maxn+5];
void dfs ( int pin, int x )
{
viz[pin][x] = 1;
if ( pin == 1 )
rez[n_ctc].push_back ( x + 1 );
int sz = g[pin][x].size (), i, nod;
for ( i = 0; i < sz; i++ )
{
nod = g[pin][x][i];
if ( !viz[pin][nod] )
dfs ( pin, nod );
}
if ( pin == 0 )
preord[ind_prd++] = x;
}
int main ()
{
ifstream fin ( "ctc.in" );
ofstream fout ( "ctc.out" );
int n, m;
fin >> n >> m;
int i, x, y;
for ( i = 0; i < m; i++ )
{
fin >> x >> y;
g[0][x-1].push_back ( y - 1 );
}
/// dfs 1
for ( i = 0; i < n; i++ )
if ( !viz[0][i] )
dfs ( 0, i );
/// transp
int j, sz;
for ( i = 0; i < n; i++ )
{
sz = g[0][i].size ();
for ( j = 0; j < sz; j++ )
g[1][g[0][i][j]].push_back ( i );
}
/// dfs 2
for ( i = n - 1; i >= 0; i-- )
{
j = preord[i];
if ( !viz[1][j] )
{
dfs ( 1, j );
n_ctc++;
}
}
fout << n_ctc << '\n';
for ( i = 0; i < n_ctc; i++ )
{
sz = rez[i].size ();
for ( j = 0; j < sz; j++ )
fout << rez[i][j] << ' ';
fout.put ( '\n' );
}
fin.close ();
fout.close ();
return 0;
}