Cod sursa(job #951607)

Utilizator Aida_SilviaStrimbeanu Aida Silvia Aida_Silvia Data 21 mai 2013 00:13:25
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

#define nmax 100073

using namespace std;

int n,m,nr_comp,c;
int viz[nmax], niv[nmax];

stack <int> s;

vector <int> g[nmax];
vector <int> sol[nmax];


void stiva(int a, int b)
{
    while (s.top()!=b)
    {
        sol[c].push_back(s.top());
        s.pop();

    }

    sol[c].push_back(b);
    sol[c].push_back(a);
    c++;

    s.pop();
}

void dfs(int a, int b )
{
    viz[a]=viz[b]+1;
    niv[a]=viz[a];

    for (unsigned int i=0; i<g[a].size(); ++i)
    {
        int nod=g[a][i];

        if (!viz[nod])
        {

            s.push(nod);
            dfs(nod,a);
            niv[a]=min(niv[a],niv[nod]);

            if (niv[nod]>=viz[a])
                stiva(a,nod);

        }
        else
        {
            if (nod!=b)
                niv[a]=min(niv[a],niv[nod]);

        }

    }
}

int main()
{
    int x,y;
    int i;

    ifstream cin("biconex.in");
    ofstream cout("biconex.out");

    cin>>n>>m;

    for (i=1; i<=m; ++i)
    {
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    s.push(1);
    dfs(1,0);

    cout<<c<<"\n";
    for( i=0; i<c; i++,cout<<"\n")
        for(int j=0; j<sol[i].size(); j++)
            cout<<sol[i][j]<<" ";

    return 0;
}