Cod sursa(job #1622234)

Utilizator Toast97Calin Farcas Toast97 Data 1 martie 2016 09:50:37
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.31 kb
#include <fstream>

using namespace std;

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

const int vecini = 0;
const int comp = 100000;
const int stiva = 200004;

struct nod
{
     int info;
     nod *adr;
} *v[200010];

void adaugare (int x, int y)
{
     nod *c;
     c = new nod;
     c -> info = y;
     c -> adr = v[x];
     v[x] = c;
}

void eliminare (int x)
{
     nod *p;
     p = v[x];
     v[x] = v[x] -> adr;

     delete p;
}

int n, m, lowlink[100005], index[100005], nrc = 0;
bool viz[100005];

void citire ()
{
     int x, y;

     f >> n >> m;

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

int minim (int a, int b)
{
     if (a < b)
          return a;
     return b;
}

void dfs (int node, int nivel)
{
     lowlink[node] = nivel;
     index[node] = nivel;
     viz[node] = 1;

     adaugare (stiva, node);

     nod *c;

     c = v[vecini + node];

     int curent;

     while (c)
     {
          curent = c -> info;

          if (viz[curent])
               lowlink[node] = minim (lowlink[node], index[curent]);
          else
          {
               dfs (curent, nivel + 1);
               lowlink[node] = minim (lowlink[node], lowlink[curent]);

               if (index[node] <= lowlink[curent])
               {
                    ++ nrc;

                    int de_adaugat;

                    do
                    {
                         de_adaugat = v[stiva] -> info;
                         adaugare (comp + nrc, de_adaugat);
                         eliminare (stiva);
                    }while (de_adaugat != curent);

                    adaugare (comp + nrc, node);
               }
          }

          c = c -> adr;
     }
}

void afisare ()
{
     g << nrc << '\n';

     for (int i = 1; i <= nrc; i ++)
     {
          while (v[comp + i])
          {
               g << v[comp + i] -> info << " ";
               eliminare (comp + i);
          }

          g << '\n';
     }

}

int main ()
{
     citire ();

     for (int i = 1; i <= n; i ++)
          if (! viz[i])
               dfs (i, 1);

     afisare ();

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