Pagini recente » Cod sursa (job #894698) | Cod sursa (job #318808) | Cod sursa (job #1227108) | Cod sursa (job #1302581) | Cod sursa (job #1082627)
#include<stdio.h>
#include<vector>
using namespace std;
FILE *in,*out;
const int Nmax=(int) 1e5+1;
int n,m;
int nod1,nod2;
int postordine[Nmax];
int nrc,rez;
vector<int> answer[Nmax];
bool viz[Nmax];
vector<int> graf[Nmax],graft[Nmax];
void dfs(int nod);
void dfst(int nod);
int main(void)
{
in=fopen("ctc.in","rt");
fscanf(in,"%d%d",&n,&m);
for(int i=0;i<m;++i)
{
fscanf(in,"%d%d",&nod1,&nod2);
graf[nod1].push_back(nod2);
graft[nod2].push_back(nod1);
}
fclose(in);
for(int i=1;i<=n;++i)
if(!viz[i])
dfs(i);
for(int i=nrc;i>=0;--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[nrc++]=nod;
}
void dfst(int nod)
{
viz[nod]=false;
answer[rez].push_back(nod);
vector<int> :: iterator it,end=graft[nod].end();
for(it=graft[nod].begin() ; it!=end ; ++it)
{
if(viz[*it])
dfst(*it);
}
}