Pagini recente » Cod sursa (job #2755881) | Cod sursa (job #1418288) | Cod sursa (job #845986) | Cod sursa (job #1814052) | Cod sursa (job #894463)
Cod sursa(job #894463)
//plus-minus
#include<fstream>
#include<algorithm>
#include<vector>
#define NN 100001
#define pb push_back
using namespace std;
ofstream out("ctc.out");
int n , m , uz1[NN] , uz2[NN] , nrp ;
vector< int > G1[NN] , G2[NN];
typedef vector< int >:: iterator IT;
void read();
void dfs( vector< int > *g , int start , int cul , int * );
void solve();
void wrs();
int main()
{
read();
solve();
wrs();
return 0;
}
void read()
{
ifstream in("ctc.in");
in >> n >> m;
for( int x , y ; m ; --m )
{
in >> x >> y;
G1[x].pb(y);
G2[y].pb(x);
}
}
void dfs( vector< int > *g , int start , int cul , int *v )
{
v[ start ] = cul;
for( IT i = g[start].begin(); i!=g[start].end(); ++i )
if ( !v[ *i ] )
dfs( g , *i , cul , v );
}
void solve()
{
for( int i=1 ; i<=n ; i++)
if ( !uz1[i] && !uz2[i] )
{
++nrp;
dfs( G1 , i , nrp , uz1 );
dfs( G2 , i , nrp , uz2 );
for( int j = 1 ; j<=n ; j++)
uz1[j] = uz2[j] = min( uz1[j] , uz2[j] );
}
}
void wrs()
{
out << nrp << '\n';
for( int i=1 ; i<=nrp ; i++)
{
for( int j=1; j<=n;j++)
if ( uz1[j] == i )
out << j << " ";
out << '\n';
}
}