Cod sursa(job #1639024)

Utilizator SchopenhauerIordache Stefan Schopenhauer Data 8 martie 2016 10:35:00
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include<iostream>
#include<fstream>
#include<cstdlib>
#include<vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int x,y,viz[100005],n,m,*a[100005],*b[100005],v[100005],graf[100005],nn;
vector <int> G[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]);
     v[nn--]=nod;}

void dfs1(int nod, int nr)
    {int i;
     graf[nod]=nr;
     for (i=1;i<=a[nod][0];i++)
           if (graf[a[nod][i]]==0)
                dfs1(a[nod][i],nr);}


int main()
   { int i,j,en,nr;
     f>>n>>m;
     nn=n;
     for (i=1;i<=n;i++)
        { a[i]=(int *)realloc(a[i],sizeof(int));
          b[i]=(int *)realloc(b[i],sizeof(int));
          a[i][0]=b[i][0]=0;}
     for (i=1;i<=m;i++)
         { f>>x>>y;
           a[x][0]++;
           a[x]=(int *)realloc(a[x],(a[x][0]+1)*sizeof(int));
           a[x][a[x][0]]=y;
           b[y][0]++;
           b[y]=(int *)realloc(b[y],(b[y][0]+1)*sizeof(int));
           b[y][b[y][0]]=x;}

     for (i=1;i<=n;i++)
          if (viz[i]==0)
               dfs(i);
    nr=1;
    en=n;
    while (en)
       {  if (graf[v[en]]==0)
             {dfs1(v[en],nr);
              nr++;}
          en--;}
    g<<nr-1<<'\n';
    for (i=1;i<nr;i++)
    {for (j=1;j<=n;j++)
             if (graf[j]==i)
                g<<j<<" ";
     g<<'\n';}
    return 0; }