Pagini recente » Cod sursa (job #2110926) | Cod sursa (job #1927599) | Cod sursa (job #785258) | Cod sursa (job #2799787) | Cod sursa (job #1662365)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int Nmax=100005;
const int Mmax=200005;
vector <int> v[100005];
int n,m,a,b,nr,nc,nrc;
int vf[Mmax],urm[Mmax],lst[Nmax],vft[Mmax],urmt[Mmax],lstt[Nmax],c[Nmax];
bool viz[Nmax];
void adauga ( int x , int y ){
nr++;
vf[nr]=y;
urm[nr]=lst[x];
lst[x]=nr;
vft[nr]=x;
urmt[nr]=lstt[y];
lstt[y]=nr;
}
void dfs ( int x ){
viz[x]=true;
int p,y;
p=lst[x];
while ( p != 0 ){
y=vf[p];
if ( !viz[y] )
dfs(y);
p=urm[p];
}
c[++nc]=x;
}
void dfst ( int x ){
viz[x]=true;
int p,y;
p=lstt[x];
v[nrc].push_back(x);
while ( p != 0 ){
y=vft[p];
if ( !viz[y] )
dfst(y);
p=urmt[p];
}
}
int main()
{
fin>>n>>m;
for ( int i=1 ; i<=m ; i++ ){
fin>>a>>b;
adauga(a,b);
}
for ( int i=1 ; i<=n ; i++ ){
if ( !viz[i] )
dfs(i);
}
for ( int i=1 ; i<=n ; i++ ){
viz[i]=false;
}
for ( int i=n ; i>=1 ; i-- ){
if ( !viz[c[i]] ){
++nrc;
dfst(c[i]);
}
}
fout<<nrc<<'\n';
for ( int i=1 ; i<=nrc ; i++ ){
for ( int j=0 ; j<v[i].size() ; j++ ){
fout<<v[i][j]<<' ';
}
fout<<'\n';
}
}