Pagini recente » Cod sursa (job #269348) | Cod sursa (job #2174058) | Cod sursa (job #3217930) | Cod sursa (job #2927378) | Cod sursa (job #1088247)
#include<stdio.h>
#include<vector>
using namespace std;
FILE *in,*out;
//definitii
#define pb push_back
//constante
const int Nmax=(int)1e5+1;
//functii
void dfs(int nod);
void dfst(int nod);
//variabile
int n,m;
int nod1,nod2,nr,rez;
int postordine[Nmax];
vector<int>graf[Nmax];
vector<int>transpus[Nmax];
vector<int>answer[Nmax];
bool viz[Nmax];
int main(void)
{
in=fopen("ctc.in","rt");
fscanf(in,"%d%d",&n,&m);
for(int i=1;i<=m;++i)
{
fscanf(in,"%d%d",&nod1,&nod2);
graf[nod1].pb(nod2);
transpus[nod2].pb(nod1);
}
fclose(in);
for(int i=1;i<=n;++i)
if(!viz[i])
dfs(i);
for(int i=n;i>=1;--i)
if(viz[postordine[i]])
{
dfst(postordine[i]);
rez++;
}
out=fopen("ctc.out","wt");
fprintf(out,"%d\n",rez);
for(int i=0;i<=rez;++i)
{
vector<int>::iterator it,end=answer[i].end();
for(it=answer[i].begin() ; it!=end ; ++it)
fprintf(out,"%d ",*it);
fprintf(out,"\n");
}
fclose(out);
return 0;
}
void dfs(int nod)
{
viz[nod]=true;
vector<int>::iterator it,end=graf[nod].end();
for(it=graf[nod].begin() ; it!=end ; ++it)
if(!viz[*it])
dfs(*it);
postordine[++nr]=nod;
}
void dfst(int nod)
{
viz[nod]=false;
answer[rez].pb(nod);
vector<int>::iterator it,end=transpus[nod].end();
for(it=transpus[nod].begin() ; it!=end ; ++it)
if(viz[*it])
dfst(*it);
}