Cod sursa(job #1643743)

Utilizator SchopenhauerIordache Stefan Schopenhauer Data 9 martie 2016 20:03:57
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include<fstream>
#include<cstdlib>
#include<cstdio>
#include<vector>
using namespace std;
FILE *f=fopen("ctc.in","r");
ofstream g("ctc.out");
int *AT[100005],*a[100005],m,n,x,y,nr_ctc,viz[100005],postord[100005],nr;
vector<int> componente[100005];


void DFS(int nod)
   { int i;
     viz[nod]=1;
     for (i=1;i<=a[nod][0];i++)
         if (viz[a[nod][i]]==0)
               DFS(a[nod][i]);
     postord[++nr]=nod; }


void DFS_t(int nod)
      { int i;
        viz[nod]=0;
        componente[nr_ctc].push_back(nod);
        for (i=1;i<=AT[nod][0];i++)
            if (viz[AT[nod][i]]==1)
                DFS_t(AT[nod][i]);}

int main()
   {  int i,j;
      fscanf(f,"%d %d",&n,&m);
      for (i=1;i<=n;i++)
         { a[i]=(int*)realloc(a[i],sizeof(int));
           AT[i]=(int*)realloc(AT[i],sizeof(int));
           a[i][0]=AT[i][0]=0;}
      for (i=1;i<=m;i++)
         {fscanf(f,"%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;}
      for (i=1;i<=n;i++)
          if (viz[i]==0)
               DFS(i);
      for (i=n;i>=1;i--)
         if (viz[postord[i]]==1)
          {nr_ctc++;
           DFS_t(postord[i]);}
      g<<nr_ctc<<'\n';
      for (i=1;i<=nr_ctc;i++)
         { for (j=0;j<componente[i].size();j++)
                   g<<componente[i][j]<<" ";
          g<<'\n';}
          return 0;}