Cod sursa(job #498938)

Utilizator Gabriela94Rus Gabriela Gabriela94 Data 7 noiembrie 2010 19:28:46
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<fstream>
#include<vector>
using namespace std;
#define Nmax 100001
vector<int> G[Nmax],Gt[Nmax],Comp[Nmax];
 
int n,m,nrc,postordine[Nmax],nr, k,vizitat[Nmax];
void citire()
{
   int i,x,y;
    ifstream f("ctc.in");
   f>>n>>m;
   for(i=1;i<=m;i++)
   {
    f>>x>>y;
   G[x].push_back(y);
  Gt[y].push_back(x);
   }
    f.close();
}
void df(int nod)
 
{
int i,vecini;
vizitat[nod]=1;
vecini=G[nod].size();
for(i=0; i < vecini; i++)
 
   if (!vizitat[G[nod][i]])
    
        df(G[nod][i]);
        
   postordine[++nr]=nod;
}


void df2(int nod)
{
    int i,vecini;
    Comp[nrc].push_back(nod);
    vizitat[nod]=0;
    vecini= Gt[nod].size();
    for(i=0;i<vecini;i++)
        if (vizitat[Gt[nod][i]])
           df2(Gt[nod][i]);
        
}

int main()
{
int i,vecini,j;
citire();
for(i=1;i<=n;i++)
    if (!vizitat[i])
       df(i);
   for(i=n;i>0;i--)
        
   if (vizitat[postordine[i]])
    {
   nrc++;
   k=0;
   df2(postordine[i]);
   }
     
   ofstream g("ctc.out");
   g<<nrc<<"\n";
    for(i=1;i<=nrc;i++)
   {
   vecini=Comp[i].size();
   for(j=0;j<vecini;j++)
       g<<Comp[i][j]<<"  ";
   g<<"\n";
   }
     
   g.close();
   return 0;
}