Pagini recente » Cod sursa (job #2585780) | Cod sursa (job #2277291) | Cod sursa (job #2173883) | Cod sursa (job #2275817) | Cod sursa (job #554100)
Cod sursa(job #554100)
#include <algorithm>
#include <bitset>
#include <fstream>
#include <vector>
using namespace std;
const char Input[] = "ctc.in";
const char Output[] = "ctc.out";
const int Dim = 100001;
int N, M;
int ncomp, ant[Dim];
bitset <Dim> f;
vector <int> v[Dim], vt[Dim], comp[Dim];
void DF( int nod ) {
vector <int> :: iterator it;
f[nod] = true;
for( it = v[nod].begin(); it != v[nod].end(); ++it )
if( f[*it] == false )
DF( *it );
ant[++ant[0]] = nod;
}
void DFT( int nod ) {
vector <int> :: iterator it;
f[nod] = false;
comp[ncomp].push_back( nod );
for( it = vt[nod].begin(); it != vt[nod].end(); ++it )
if( f[*it] == true )
DFT( *it );
}
int main() {
ifstream fin( Input );
ofstream fout( Output );
int i, x, y;
vector <int> :: iterator it;
fin >> N >> M;
while( M-- ) {
fin >> x >> y;
v[x].push_back( y );
vt[y].push_back( x );
}
for( i = 1; i <= N; ++i )
if( f[i] == false )
DF( i );
for( i = N; i >= 1; --i )
if( f[ant[i]] == true ) {
++ncomp;
DFT( ant[i] );
}
fout << ncomp << "\n";
for( i = 1; i <= ncomp; fout << "\n", ++i )
for( it = comp[i].begin(); it != comp[i].end(); ++it )
fout << *it << " ";
fin.close();
fout.close();
return 0;
}