Cod sursa(job #528797)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 3 februarie 2011 14:43:06
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#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;}