Cod sursa(job #520772)

Utilizator giuliastefGiulia Stef giuliastef Data 10 ianuarie 2011 12:37:28
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
#include <vector>
#define MAXN 100010
using namespace std;
int n,m,vizitat[MAXN],final[MAXN],ordine[MAXN],timp,nr,ap[MAXN];
vector <int> graf[MAXN],graft[MAXN],sol[MAXN];
void df_final(int nod)
{
     int i;
     vizitat[nod]=1;
     for(i=0;i<graf[nod].size();i++)
      if(!vizitat[graf[nod][i]])
       df_final(graf[nod][i]);
     timp++;
     final[nod]=timp;
      
}
void stabilire_ordine()
{
     int i,k;
     for(i=1;i<=n;i++)
      {
       k=final[i];
       ordine[n-k+1]=i;
      }
}
void df(int nod)
{
     int i;
     for(i=0;i<graft[nod].size();i++)
      if(!vizitat[graft[nod][i]])
      {
       vizitat[graft[nod][i]]=1;
       sol[nr].push_back(graft[nod][i]);
       df(graft[nod][i]);
      }
}
int main()
{
    int i,j,x,y,k;
    ifstream f("ctc.in");
    ofstream g("ctc.out");
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
     f>>x>>y;
     graf[x].push_back(y);
     graft[y].push_back(x);
    }
    for(i=1;i<=n;i++)
     if(!vizitat[i])
      df_final(i);
    stabilire_ordine();
    for(i=1;i<=n;i++)
     vizitat[i]=0;
    for(i=1;i<=n;i++)
    {
                     k=ordine[i];
                     if(!vizitat[k])
                     {
                      nr++;
                      vizitat[k]=1;
                      sol[nr].push_back(k);
                      df(k);
                     }
    }
    g<<nr<<"\n";
    for(i=1;i<=nr;i++)
    {
     for(j=0;j<sol[i].size();j++)
      g<<sol[i][j]<<" ";
     g<<"\n";
    }
    return 0;
}