Pagini recente » Cod sursa (job #2090349) | Cod sursa (job #2128794) | Cod sursa (job #416510) | Cod sursa (job #13304) | Cod sursa (job #1038344)
#include <cstdio>
#include <vector>
#define NMAX 100000
using namespace std;
FILE *fin,*fout;
vector <int> M[NMAX],MT[NMAX],v[NMAX];
int use[NMAX],postordine[NMAX],adaugat[NMAX];
int n,m,cat,z,CAT;
void DFS(int);
void DFST(int);
int main()
{
fin=fopen("ctc.in","r");
fout=fopen("ctc.out","w");
int i,k,x,j,dim;
fscanf(fin,"%d%d",&n,&m);
for(i=1;i<=m;i++)
{
fscanf(fin,"%d%d",&k,&x);
M[k].push_back(x);
MT[x].push_back(k);
}
for(i=1;i<=n;i++)
if(use[i]==0)
{
use[i]=1;
DFS(i);
}
for(i=n;i>=1;i--)
use[i]=0;
for(i=cat;i>=1;i--)
if(use[postordine[i]]==0)
{
CAT++;
v[CAT].push_back(postordine[i]);
use[postordine[i]]=1;
DFST(postordine[i]);
}
fprintf(fout,"%d\n",CAT);
for(i=1;i<=CAT;i++)
{
dim=v[i].size();
for(j=0;j<dim;j++)
fprintf(fout,"%d ",v[i][j]);
fprintf(fout,"\n");
}
return 0;
}
void DFST(int x)
{
int i=0,dim;
dim=MT[x].size();
for(i=0;i<dim;i++)
{ if(use[MT[x][i]]==0)
{
use[MT[x][i]]=1;
DFST(MT[x][i]);
v[CAT].push_back(MT[x][i]);
}
}
}
void DFS(int x)
{
int i,dim;
dim=M[x].size();
for(i=0;i<dim;i++)
{
if(use[M[x][i]]==0)
{
use[M[x][i]]=1;
DFS(M[x][i]);
}
if(adaugat[i])
{
cat++;
adaugat[x]=1;
postordine[cat]=x;
}
}
cat++;
adaugat[x]=1;
postordine[cat]=x;
}