Cod sursa(job #238546)

Utilizator zbarniZajzon Barna zbarni Data 2 ianuarie 2009 16:01:20
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include<stdio.h>
#include<stdlib.h>
#define nmax 100006
int *a[nmax],*at[nmax],*rez[nmax];
int po[nmax],viz[nmax],n,nr,nrc;
void read()
 {
  freopen("ctc.in","r",stdin);
  freopen("ctc.out","w",stdout);
  int m,x,y,i;
  scanf("%d %d",&n,&m);
  for (i=1;i<=n;i++)
   {
    a[i]=(int *)realloc(a[i],sizeof(int));
    a[i][0]=0;
    at[i]=(int *)realloc(at[i],sizeof(int));
    at[i][0]=0;
   }
  for (i=1;i<=m;i++)
   {
    scanf("%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;
    at[y][0]++;
    at[y]=(int *)realloc(at[y],(at[y][0]+1)*sizeof(int));
    at[y][at[y][0]]=x;
   }
 }
void dfst(int x)
 {
  int i;
  viz[x]=0;
  ++rez[nrc][0];
  rez[nrc]=(int *)realloc(rez[nrc],(rez[nrc][0]+1)*sizeof(int));
  rez[nrc][rez[nrc][0]]=x;
  for (i=1;i<=at[x][0];i++)
   if (viz[at[x][i]])
     dfst(at[x][i]);
 }
void dfs(int x)
 {
  int i;
  viz[x]=1;
  for (i=1;i<=a[x][0];i++)
    if (!viz[a[x][i]])
      dfs(a[x][i]);
  po[++nr]=x;
 }
int main()
 {
  read();
  int i;
  for (i=1;i<=n;i++)
    if (!viz[i])       dfs(i);
  for (i=n;i>0;i--)
   if (viz[po[i]])
    {
     ++nrc;
     rez[nrc]=(int *)realloc(rez[nrc],sizeof(int));
     rez[nrc][0]=0;
     dfst(po[i]);
    }
  printf("%d",nrc);
  int j;
  for(i=1;i<=nrc;++i)
    {
     printf("\n");
     for (j=1;j<=rez[i][0];++j)
      printf("%d ",rez[i][j]);
    }
  printf("\n");
  return 0;
 }