Cod sursa(job #539255)

Utilizator nickyyLal Daniel Emanuel nickyy Data 22 februarie 2011 19:17:49
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define MaxN 100005
#define min(a,b) (a<b ? a:b)
int vf_index[MaxN],low[MaxN],in_stiva[MaxN],s[MaxN];
int *comp[MaxN],*a[MaxN];
int n,index,nrcomp,nrvf;

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

    void componente(int u)
    {   int v;
        vf_index[u]=low[u]=++index;
        s[nrvf++]=u; in_stiva[u]=1;
        for(int i=1;i<=a[u][0];i++)
        {   v=a[u][i];
            if(!vf_index[v])
            {   componente(v);
                low[u]=min(low[u],low[v]);
            }
            else
                if(in_stiva[v]) low[u]=min(low[u],vf_index[v]);
        }
        if(vf_index[u]==low[u])
        {   nrcomp++;
            comp[nrcomp]=(int*)realloc(comp[nrcomp],sizeof(int));
            comp[nrcomp][0]=0;
            do
            {   v=s[--nrvf]; in_stiva[v]=0;
                comp[nrcomp][0]++;
                comp[nrcomp]=(int*)realloc(comp[nrcomp],(comp[nrcomp][0]+1)*sizeof(int));
                comp[nrcomp][comp[nrcomp][0]]=v;
            }while (v!=u);
        }
    }

    void tarjan(void)
    {   index=nrvf=nrcomp=0;
        for(int k=1;k<=n;k++)
            if(!vf_index[k]) componente(k);
    }

    void scrie(void)
    {   FILE *fout=fopen("ctc.out","w");
        fprintf(fout,"%d\n",nrcomp);
        for(int k=1;k<=nrcomp;k++)
        {   for(int i=comp[k][0];i>0;i--)
                fprintf(fout,"%d ",comp[k][i]);
            fprintf(fout,"\n");
        }
        fclose(fout);
    }

int main(void)
{   citire();
    tarjan();
    scrie();
    return 0;
}