Pagini recente » Cod sursa (job #1654689) | Cod sursa (job #2946245) | Cod sursa (job #1865507) | Cod sursa (job #1981697) | Cod sursa (job #582801)
Cod sursa(job #582801)
#include <cstdio>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <vector>
#define Nmx 100001
using namespace std;
int n,m,nr,nrs,viz[Nmx],prec[Nmx*2];
struct nod
{
int inf;
nod *urm;
};
nod *G[Nmx],*GT[Nmx];
vector<int> sol[Nmx];
ifstream fin("ctc.in");
void add(int x,int y)
{
nod *aux=new nod;
aux->inf = y;
aux->urm = G[x];
G[x]=aux;
}
void addt(int x,int y)
{
nod *aux=new nod;
aux->inf = y;
aux->urm = GT[x];
GT[x]=aux;
}
void read()
{
int x,y;
fin>>n>>m;
for(int i=1;i<=m;++i)
{
fin>>x>>y;
add(x,y);
addt(y,x);
}
}
void dfs(int x)
{
viz[x]=1;
for(nod *p=G[x];p;p=p->urm)
if(!viz[p->inf])
dfs(p->inf);
prec[++nr]=x;
}
void dfst(int x)
{
viz[x]=0;
sol[nrs].push_back(x);
for(nod *p=GT[x];p;p=p->urm)
if(viz[p->inf])
dfst(p->inf);
}
void solve()
{
for(int i=1;i<=n;++i)
if(!viz[i])
dfs(i);
for(int i=nr;i>=1;--i)
if(viz[prec[i]])
{
++nrs;
dfst(prec[i]);
}
printf("%d\n",nrs);
for(int i=1;i<=nrs;++i)
{
for(int j=0;j<sol[i].size();++j)
printf("%d ",sol[i][j]);
printf("\n");
}
}
int main()
{
freopen("ctc.out","w",stdout);
read();
solve();
return 0;
}