Cod sursa(job #1279040)

Utilizator robertstrecheStreche Robert robertstreche Data 29 noiembrie 2014 18:08:20
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <vector>
#include <stack>

#define lmax 100005
#define pb push_back
#define mp make_pair

using namespace std;

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

vector <int> v[lmax],sol[lmax];

stack <pair<int,int> >s;

int mi[lmax],urm[lmax];
int n,m,i,nr,x,y;

inline void dfs(int nod,int nivel,int tata)
{
    vector <int>::iterator it;

    mi[nod]=nivel;

    for (it=v[nod].begin();it!=v[nod].end();it++)
     if (*it!=tata)
      if (!mi[*it])
        {
             s.push(mp(nod,*it));
             urm[nod]=*it;
             dfs(*it,nivel+1,nod);

             mi[nod]=mi[*it]<mi[nod]?mi[*it]:mi[nod];

             if (mi[*it]>=nivel)
              {
                 sol[++nr].pb(nod);
                 while (s.top().first!=nod)
                  {
                      sol[nr].pb(s.top().second);
                      s.pop();
                  }
                 sol[nr].pb(s.top().second);
                 s.pop();
               }
        }
       else
         mi[nod]=mi[*it]<mi[nod]?mi[*it]:mi[nod];

}
int main()
{
    vector <int>::iterator it;

    f>>n>>m;

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

         v[x].pb(y);
         v[y].pb(x);
     }

    dfs(1,1,0);

    g<<nr<<'\n';

    for (i=1;i<=nr;i++)
     {
         for (it=sol[i].begin();it!=sol[i].end();it++)
          g<<*it<<" ";

         g<<'\n';
     }

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