Cod sursa(job #527829)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 1 februarie 2011 12:51:32
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<iostream.h>
#include<fstream.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};

void dfr1(long i)
{long j;
suc[i]=nrc;
for(j=deg1[i]-1;j>=0;j--)
if(suc[g1[i][j]]==0)
      dfr1(g1[i][j]);}

void dfr2(long i)
{long j;
pred[i]=nrc;
for(j=deg2[i]-1;j>=0;j--)
if(pred[g2[i][j]]==0)
      dfr2(g2[i][j]);}

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(suc[i]==0)
       {dfr1(i);
       dfr2(i);
       nrc++;}
f2<<nrc-1<<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;}