Cod sursa(job #1529710)

Utilizator VictoriaNevTascau Victoria VictoriaNev Data 21 noiembrie 2015 10:48:21
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int NMAX=100001;
int n, m, nr, levelnr;
vector<int> sol[NMAX], g[NMAX];
int low[NMAX], level[NMAX];
stack<int> st;
void update(int u, int v)
{
    nr++;
    while(st.top()!=v)
    {
        sol[nr].push_back(st.top());
        st.pop();
    }
    sol[nr].push_back(u);
    sol[nr].push_back(v);
    st.pop();
}
void dfs(int x, int parent)
{
    levelnr++;
    level[x]=levelnr;
    low[x]=levelnr;
    for(int i=0; i<g[x].size(); i++)
        if(g[x][i]!=parent)
            if(!level[g[x][i]])
            {
                st.push(g[x][i]);
                dfs(g[x][i], x);
                low[x]=min(low[x], low[g[x][i]]);
                if(low[g[x][i]]>=level[x])update(x, g[x][i]);
            }
            else low[x]=min(low[x], level[g[x][i]]);
}
int main()
{
    ifstream in("biconex.in");
    ofstream out("biconex.out");
    int u, v, i, j;
    in>>n>>m;
    for( ; m; m--)
    {
        in>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    out<<nr<<'\n';
    for(i=1; i<=nr; i++)
    {
        for(j=0; j<sol[i].size(); j++)
            out<<sol[i][j]<<' ';
        out<<'\n';
    }
    return 0;
}