Cod sursa(job #363183)

Utilizator PopaStefanPopa Stefan PopaStefan Data 12 noiembrie 2009 09:06:55
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<fstream>
#define nmax 5001


using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int l[nmax][nmax],n,m,a[nmax][nmax],numar=1;
int nr,viz[nmax],postordine[nmax];
int comp[nmax];

void citire()
{int i,m,x,y;
fin>>n>>m;
for(i=1;i<=m;i++)
  {fin>>x>>y;
  l[x][0]++;
  l[x][l[x][0]]=y;
  a[y][0]++;
  a[y][a[y][0]]=x;
  }
}

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

void dfst(int x)
{int i;
viz[x]=0;
comp[x]=numar;
for(i=1;i<=a[x][0];i++)
  if(viz[a[x][i]]==1)
    dfst(a[x][i]);
}

int main()
{int i,j;
citire();
for(i=1;i<=n;i++)
  if(viz[i]==0) dfs(i);
for(i=n;i>=1;i--)
   if(viz[postordine[i]])
     {dfst(postordine[i]);
     numar++;
     }
fout<<numar-1<<'\n';
for(j=1;j<=numar;j++)
  {for(i=1;i<=n;i++)
     if(comp[i]==j)
       fout<<i<<' ';
  fout<<'\n';
  }
fin.close();
fout.close();
return 0;
}