Cod sursa(job #295865)

Utilizator otilia_sOtilia Stretcu otilia_s Data 3 aprilie 2009 18:56:14
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NMAX 100005
int *L[NMAX],c[NMAX],elem[NMAX],index[NMAX],low[NMAX],S[NMAX];
int n,nc,ne,nrord,ns;
int inSt[NMAX];

void citire()
{
 FILE *fin=fopen("ctc.in","r");
 int m,i;
 fscanf(fin,"%d%d",&n,&m);
 for (i=1;i<=n;++i) 
  { L[i]=(int*)realloc(L[i],sizeof(int)); L[i][0]=0; }
 while (m--)
  { int x,y;
    fscanf(fin,"%d %d",&x,&y);
    L[x][0]++;
    L[x]=(int*)	realloc(L[x],(L[x][0]+1)*sizeof(int));
    L[x][L[x][0]]=y;    
  }
 fclose(fin);
}

void afisare()
{
 FILE *fout=fopen("ctc.out","w");
 fprintf(fout,"%d",nc);
 c[0]=0;
 int i;
 for (i=1;i<=n;++i)
  {
   if (c[i]!=c[i-1]) fprintf(fout,"\n");
   fprintf(fout,"%d ",elem[i]);
  }
 fclose(fout);
}

inline int min(int a, int b)
{
 if (a<b) return a;
 return b;
}

void tarjan(int v)
{ int i;
 index[v]=low[v]=++nrord; 
 S[++ns]=v;inSt[v]=1;
 for (i=1;i<=L[v][0];++i)
  {
   int w=L[v][i];
   if (!index[w] || inSt[w])
    {
     if (!index[w]) tarjan(w);
     low[v]=min(low[v],low[w]);
    }
  }
  int w;
 if (low[v]==index[v])
  { nc++;
   do
    {
     w=S[ns--];
     elem[++ne]=w; c[ne]=nc;
    }
   while (w!=v);
  }
}

int main()
{
 citire();
 ns=0; nrord=0; ne=0;
 memset(index,0,sizeof(index));
 memset(inSt,0,sizeof(inSt));
 int i;
 for (i=1;i<=n;++i)
  if (!index[i]) tarjan(i);
 afisare();
 return 0;
}