Cod sursa(job #285479)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 22 martie 2009 17:05:04
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <stdio.h>
#include <stdlib.h>

int *a1[100001];
int *a2[100001];
int *a3[100001];
int n,m,viz[100001],ord1[100001],nrc,nr,x,y;

void dfs1(int nod)
{
    int i;
    viz[nod]=1;
    for (i=1;i<=a1[nod][0];++i)
          if (!viz[a1[nod][i]])
               dfs1(a1[nod][i]);
    ord1[++nr]=nod;
}

void dfs2(int nod)
{
    int i;
    a3[nrc][0]++;
    a3[nrc]=(int *)realloc(a3[nrc],(a3[nrc][0]+1)*sizeof(int));
    a3[nrc][a3[nrc][0]]=nod;

    viz[nod]=0;
    for (i=1;i<=a2[nod][0];++i)
          if (viz[a2[nod][i]])
               dfs2(a2[nod][i]);
}


int main()
{
    int i,j;
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);

    scanf("%d %d", &n,&m);

    for (i=1;i<=n;++i)
    {
        a1[i]=(int *) realloc(a1[i], sizeof(int));
        a1[i][0]=0;
        a2[i]=(int *) realloc(a2[i], sizeof(int));
        a2[i][0]=0;
		a3[i]=(int *) realloc(a3[i], sizeof(int));
		a3[i][0]=0;
    }

    for (i=1;i<=m;++i)
    {
        scanf("%d %d", &x,&y);
        a1[x][0]++;
        a1[x]=(int *)realloc(a1[x],(a1[x][0]+1)*sizeof(int));
        a1[x][a1[x][0]]=y;
        a2[y][0]++;
        a2[y]=(int *)realloc(a2[y],(a2[y][0]+1)*sizeof(int));
        a2[y][a2[y][0]]=x;
    }
    for (i=1;i<=n;++i)
         if (!viz[i])
              dfs1(i);
    for (i=n;i>0;--i)
        if (viz[ord1[i]])
            {
              nrc++;
              dfs2(ord1[i]);
            }
    printf("%d\n", nrc);
    for (i=1;i<=nrc;++i)
    {
    for(j=1;j<=a3[i][0];++j)
        printf("%d ", a3[i][j]);
        printf("\n");
    }

    return 0;
}