Pagini recente » Cod sursa (job #802072) | Cod sursa (job #2738567) | Cod sursa (job #1573021) | Cod sursa (job #2275071) | Cod sursa (job #782135)
Cod sursa(job #782135)
#include<fstream>
using namespace std;
typedef struct lnod{
int vf;
struct lnod *next;
}*Nod;
const int NM=100003;
Nod G[NM],T[NM],S[NM];
int e[NM+NM],lev,ne;
bool viz[NM];
void add(Nod &q,int x){
Nod p=new lnod;
p->vf=x;
p->next=q;
q=p;
}
void dfs1(int nod){
viz[nod]=1;
e[++ne]=nod;
for(Nod p=G[nod];p;p=p->next)
if(!viz[p->vf])
{
dfs1(p->vf);
e[++ne]=nod;
}
}
void dfs2(int nod){
add(S[lev],nod);
viz[nod]=0;
for(Nod p=T[nod];p;p=p->next)
if(viz[p->vf])
{
viz[p->vf]=0;
dfs2(p->vf);
}
}
int main(void){
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int i,N,M,x,y;
fin>>N>>M;
for(i=1;i<=M;++i)
{
fin>>x>>y;
add(G[x],y);
add(T[y],x);
}
dfs1(1);
for(i=ne;i>0;--i)
if(viz[e[i]])
{
++lev;
dfs2(e[i]);
}
fout<<lev<<'\n';
for(i=1;i<=lev;++i){
for(Nod p=S[i];p;p=p->next)
fout<<p->vf<<' ';
fout<<'\n';
}
return 0;
}