Cod sursa(job #1609975)

Utilizator sorynsooSorin Soo sorynsoo Data 23 februarie 2016 10:31:51
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");

#define MAXN 100005
vector<int> graf[MAXN], rasp[MAXN];
stack<int> st;

int n,m,x,y,i,j, cbc ;
int nivel[MAXN], low[MAXN];

void scoate(int nod, int next)
{
    while(st.top() != next)
    {
        rasp[cbc].push_back(st.top());
        st.pop();
    }
    st.pop();
    rasp[cbc].push_back(nod);
    rasp[cbc].push_back(next);
}

void dfs(int nod, int k)
{
    nivel[nod]=low[nod]=k;

    for(int i=0; i<graf[nod].size(); i++)
    {
        int next=graf[nod][i];
        if(!nivel[next])
        {
            st.push(next);
            dfs(next,k+1);
            low[nod] = min(low[nod], low[next]);
            if(low[ next ] >= nivel [ nod ])
            {
                cbc++;
                scoate(nod,next);
            }
        }
        else
            low[nod] = min(low[nod], nivel[next]);
    }
}
int main()
{
    cin>>n>>m;
    for(i=1; i<=m; i++)
    {
        cin>>x>>y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }
    st.push(1);
    dfs(1,1);
    cout<<cbc<<"\n";
    for(i=1; i<=cbc; i++)
    {
        for(j=0; j<rasp[i].size(); j++)
            cout<<rasp[i][j]<<" ";
        cout<<"\n";
    }
    return 0;
}