Cod sursa(job #1201942)

Utilizator robertstrecheStreche Robert robertstreche Data 26 iunie 2014 14:56:26
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <vector>
#include <bitset>

#define lmax 100005

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

vector <int> vi[lmax],vo[lmax],ordine,comp[lmax];

bitset <lmax>ap;

int n,m,nrcomponente;

int grup[lmax];

inline void read()
{
    int x,y;

    f>>n>>m;

    for (int i=1;i<=m;i++)
     {
         f>>x>>y;

         vo[x].push_back(y);
         vi[y].push_back(x);
     }
}

inline void parcurgere1(int nod)
{
    vector <int>:: iterator it;

    ap[nod]=1;

    for (it=vo[nod].begin();it<vo[nod].end();it++)
      if (ap[*it]==0)
       parcurgere1(*it);

     ordine.push_back(nod);

}

inline void parcurgere2(int nod,int nr)
{
    vector <int>::iterator it;

    grup[nod]=nr;

    for (it=vi[nod].begin();it<vi[nod].end();it++)
      if (!grup[*it])
       parcurgere2(*it,nr);

}

inline void solve()
{

    for (int i=1;i<=n;i++)
     if (!ap[i])
      parcurgere1(i);

    for (;ordine.size();ordine.pop_back())
      if (!grup[ordine.back()])
       {
           nrcomponente++;
           parcurgere2(ordine.back(),nrcomponente);
       }

     for (int i=1;i<=n;i++)
      comp[grup[i]].push_back(i);
}

inline void write()
{
    g<<nrcomponente<<'\n';

    for (int i=1;i<=nrcomponente;i++)
      {
          for (int j=0;j<comp[i].size();j++)
              g<<comp[i][j]<<" ";

          g<<'\n';
      }
}

int main()
{
    read();

    solve();

    write();

   f.close();
   g.close();
}