Cod sursa(job #1378189)

Utilizator bogdanboboc97Bogdan Boboc bogdanboboc97 Data 6 martie 2015 10:56:21
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector< vector<int> > a,sol;
vector<int> low,lvl;
stack<int> st;
int k,level,n,m;
void updatesol(int x,int y)
{
    k++;
    while(st.top()!=y)
    {
        sol[k].pb(st.top());
        st.pop();
    }
    sol[k].pb(x);sol[k].pb(y);
    st.pop();
}
void df(int x,int fth)
{
	level++;
    lvl[x]=low[x]=level;
    for(auto i: a[x])
    if(i!=fth)
    {
        if(lvl[i]==0)
        {
            st.push(i);
            df(i,x);
            low[x]=min(low[x],low[i]);
            if(low[i]>=lvl[x])updatesol(x,i);
        }
        else low[x]=min(low[x],lvl[i]);
    }
}
int main()
{
    in>>n>>m;
    a=sol=vector< vector<int> >(n+1);
    low=lvl=vector<int>(n+1);
    for(;m;m--)
    {
        int x,y;
        in>>x>>y;
        a[x].pb(y);
        a[y].pb(x);
    }
    df(1,0);
    out<<k<<'\n';
    for(int i=1;i<=k;i++,cout<<'\n')
        for(auto j: sol[i])
        out<<j<<' ';
    return 0;
}