Cod sursa(job #641611)

Utilizator AnaTudorTudor Ana Maria Mihaela AnaTudor Data 28 noiembrie 2011 22:52:01
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<stdio.h>
#include<vector>
# define max 100005
using namespace std;

vector<int> graf[max],graftrans[max],tts[max];
int stiva[max],vf=0,conex;
bool viz[max];

void df1(int nod)
{ int i;
    viz[nod]=1;

  for(i=0;i<graf[nod].size();++i)
   {

    if (!viz[graf[nod][i]])
      df1(graf[nod][i]);
   }

  stiva[vf]=nod;
  vf++;
}

void df2(int nod)
{  viz[nod]=0;
  tts[conex].push_back(nod);
  for(int i=0;i<graftrans[nod].size();++i)
    if (viz[graftrans[nod][i]])
      df2(graftrans[nod][i]);
}
int main()
{int n,m,x,y;;
 freopen("ctc.in","r",stdin);
 freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for ( int i=0;i<m;++i)
 {
     scanf("%d%d",&x,&y);
     graf[x].push_back(y);
     graftrans[y].push_back(x);
}
 for(int i=1;i<=n;++i)
   if(!viz[i])
     df1(i);

conex=0;
for (int j=n-1;j>=0;j--)
 if (viz[stiva[j]])
 {df2(stiva[j]);
 conex++;
 }
printf("%d\n",conex);
for (int i=0;i<conex;++i)
 { for(int j=0;j<tts[i].size();++j)
     printf("%d ",tts[i][j]);
  printf("\n");
}

return 0;
}