Pagini recente » Cod sursa (job #1906371) | Cod sursa (job #1361526) | Cod sursa (job #1416565) | Cod sursa (job #2071987) | Cod sursa (job #528797)
Cod sursa(job #528797)
#include<iostream.h>
#include<fstream.h>
#include<stdlib.h>
#define N 100001
#define M 200001
long n,m,a[M],b[M],deg1[N]={0},deg2[N]={0},*g1[N],*g2[N],i,j,k,nrc=1,suc[N]={0},pred[N]={0},c[N]={0},l;
void dfr(long *g[N],long deg[N],long i,long s[N])
{long j;
s[i]=nrc;
for(j=deg[i]-1;j>=0;j--)
if(s[g[i][j]]==0)
dfr(g,deg,g[i][j],s);}
int main()
{ifstream f1("ctc.in");
ofstream f2("ctc.out");
f1>>n>>m;
for(i=1;i<=m;i++)
{f1>>a[i]>>b[i];
deg2[a[i]]++;
deg1[b[i]]++;}
for(j=1;j<=n;j++)
{g1[j]=(long*)malloc((deg1[j]+1)*sizeof(long));
g2[j]=(long*)malloc((deg2[j]+1)*sizeof(long));
deg1[j]=0;
deg2[j]=0;}
for(k=1;k<=m;k++)
{g1[b[k]][deg1[b[k]]++]=a[k];
g2[a[k]][deg2[a[k]]++]=b[k];}
for(i=1;i<=n;i++)
if(c[i]==0)
{dfr(g1,deg1,i,suc);
dfr(g2,deg2,i,pred);
nrc++;}
for(l=1;l<=n;l++)
if(suc[l]!=pred[l])
suc[l]=pred[l]=nrc++;
f2<<nrc<<endl;
for(j=1;j<nrc;j++)
{for(k=1;k<=n;k++)
if(suc[k]==j&&pred[k]==j)
f2<<k<<" ";
f2<<endl;}
f1.close();
f2.close();
return 0;}