Cod sursa(job #245393)

Utilizator zbarniZajzon Barna zbarni Data 17 ianuarie 2009 22:29:35
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<fstream.h>
#include<stdlib.h>
#define nmax 100005
int *a[nmax],*at[nmax],*rez[nmax];
int pos[nmax],viz[nmax],n,m,nr,nrc;

void dfs (int x)
 {
  viz[x]=1;
  for (int i=1;i<=a[x][0];++i)
    if (viz[a[x][i]])
      dfs(a[x][i]);
  pos[++nr]=x;
 }

void dfst(int x)
 {
  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 (int i=1;i<=at[x][0];++i)
     if (viz[at[x][i]])
       dfst(at[x][i]);
 }

int main()
 {
  ifstream be ("ctc.in");
  ofstream ki ("ctc.out");
  be>>n>>m;
  int i,x,y;
  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)
    {
     be>>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;
    }
  for (i=1;i<=n;++i)
    if (!viz[i])
       dfs(i);
  for (i=n;i;--i)
    {
     if (viz[pos[i]])
      {
       ++nrc;
       rez[nrc]=(int*)realloc(rez[nrc],sizeof(int));
       rez[nrc][0]=0;
       dfst(pos[i]);
      }
    }
  ki<<nrc<<'\n';
  for (i=1;i<=nrc;++i)
   {
    for (int j=1;j<=rez[i][0];++j)
      ki<<rez[i][j]<<' ';
    ki<<'\n';
   }
  ki.close();
  return 0;
 }