Cod sursa(job #520598)

Utilizator giuliastefGiulia Stef giuliastef Data 9 ianuarie 2011 17:19:53
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.89 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];
struct solutie{
       int nod, comp;
       } sol[MAXN];
bool cmp(solutie a, solutie b)
{
  if(a.comp>b.comp)
   return 0;
  else
   if(a.comp<b.comp)
    return 1;
   else
    if(a.comp==b.comp)
     if(a.nod>b.nod)
      return 0;
     else
      return 1;
}
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[graft[nod][i]].nod=graft[nod][i];
       sol[graft[nod][i]].comp=nr;
       df(graft[nod][i]);
      }
}
int main()
{
    int i,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);
    }
    df_final(1);
    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[k].nod=k;
                      sol[k].comp=nr;
                      df(k);
                     }
    }
  //  sort(sol+1,sol+n+1,cmp);
    g<<nr<<"\n";
    g<<sol[1].nod<<" ";
    for(i=2;i<=n;i++)
    {
     if(sol[i].comp>sol[i-1].comp)
      g<<"\n";
     g<<sol[i].nod<<" ";
    }
    g<<"\n";
    return 0;
}