Pagini recente » Cod sursa (job #1430476) | Cod sursa (job #1907902) | Cod sursa (job #1043337) | Cod sursa (job #409479) | Cod sursa (job #2509828)
#include <bits/stdc++.h>
#define Nmax 100005
using namespace std;
ifstream fin ( "ctc.in" );
ofstream fout ( "ctc.out" );
vector < int > g[Nmax], gt[Nmax], rev, cicle[Nmax/3];
bitset < Nmax > b;
int n, m, contor;
void read ( );
void DFS ( int x );
void DFS2 ( int x );
int main ( )
{
read ( );
for ( int i = 1; i <= n; i++ )
if ( b[i] == 0 )
DFS ( i );
int lng = rev.size();
b.reset();
for ( int i = lng - 1; i >=0 ; i-- )
{
if ( b[rev[i]] == 0 )
contor++,DFS2 ( rev[i] );
}
for ( int i = 1; i <= contor; i++ )
{
lng = cicle[i].size();
for ( int j = 0; j < lng ; j++ )
fout << cicle[i][j] << ' ';
fout << '\n';
}
}
void DFS2 ( int x )
{
b[x] = 1;
int lng = gt[x].size(), node;
for ( int i = 0; i < lng ; i++ )
{
node = gt[x][i];
if ( b[node] == 0 )
DFS2 ( node );
}
cicle[contor].push_back(x);
}
void DFS ( int x )
{
b[x] = 1;
int lng = g[x].size(), node;
for ( int i = 0; i < lng ; i++ )
{
node = g[x][i];
if ( b[node] == 0 )
DFS ( node );
}
rev.push_back(x);
}
void read ( )
{
int x, y;
fin >> n >> m;
for ( int i = 1; i <= m; i++ )
{
fin >> x >> y;
g[x].push_back(y);
gt[y].push_back(x);
}
}