Cod sursa(job #285530)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 22 martie 2009 18:06:31
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<stdio.h>
#include<string>
#include<vector>
using namespace std;
FILE*fin=fopen("ctc.in","r");
FILE*fout=fopen("ctc.out","w");
#define nm 100005
#define pb push_back 
int n,m,stiva[nm],nrctc=0,ds=0;
char viz[nm];
vector<int> g[nm],gt[nm],ctc[nm];
void df(int nod)
{
  viz[nod]=1;
  int i,nnod;
  for(i=0;i<g[nod].size();i++)
  {
    nnod=g[nod][i];
    if(!viz[nnod]) df(nnod);
  }  
  ds++;stiva[ds]=nod;
}
void dft(int nod)
{
  viz[nod]=0;
  ctc[nrctc].pb(nod);
  int i,nnod;
  for(i=0;i<gt[nod].size();i++)
  {
    nnod=gt[nod][i];
    if(viz[nnod]) dft(nnod);
  }
}
int main()
{
  int a,b,i,j;
  fscanf(fin,"%d%d",&n,&m);  
  for(i=1;i<=m;i++)
  {
    fscanf(fin,"%d%d",&a,&b);
    g[a].pb(b);
    gt[b].pb(a);
  }
  memset(viz,0,sizeof(viz));
  for(i=1;i<=n;i++)
    if(!viz[i]) df(i);
  for(i=n;i>=1;i--)
    if(viz[stiva[i]])
    {
      nrctc++;
      dft(stiva[i]);
    }  
  fprintf(fout,"%d\n",nrctc);  
  for(i=1;i<=nrctc;i++)
  { 
     for(j=0;j<ctc[i].size();j++)
       fprintf(fout,"%d ",ctc[i][j]);
     fprintf(fout,"\n");   
  }  
  fclose(fin);
  fclose(fout);
  return 0;
}