Cod sursa(job #950914)

Utilizator vladm97Matei Vlad vladm97 Data 18 mai 2013 18:23:00
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#define lmax 110000

using namespace std;

int n,m,lev[lmax],c;
vector<int> G[lmax],sol[lmax];
stack<int> s;
int use[lmax];

void sp(int x, int y)
{
     while(s.top()!=y)
    {
        sol[c].push_back(s.top());
        s.pop();
    }
    sol[c].push_back(y);
    sol[c++].push_back(x);
    s.pop();
}

void df(int a, int t)
{
    use[a]=use[t]+1;
    lev[a]=use[a];
    for(int i=0;i<G[a].size();i++)
    {
        if(!use[G[a][i]])
        {
            s.push(G[a][i]);
            df(G[a][i],a);
            lev[a]=min(lev[a],lev[G[a][i]]);
            if(lev[G[a][i]]>=use[a])
            {
                sp(a,G[a][i]);
            }
        }
        else
        {
            if(G[a][i]!=t)
            {
                lev[a]=min(lev[a],lev[G[a][i]]);
            }
        }
    }
}
int main()
{
    ifstream f("biconex.in");
    ofstream g("biconex.out");
    f>>n>>m;
    int x,y;
    for(int i=0;i<m;i++)
    {
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    s.push(1);
    df(1,0);
    g<<c<<'\n';
    for(int i=0;i<c;i++,g<<'\n')
        for(int j=0;j<sol[i].size();j++)
            g<<sol[i][j]<<' ';
    f.close();
    g.close();
}