Cod sursa(job #1650156)

Utilizator sorynsooSorin Soo sorynsoo Data 11 martie 2016 16:52:26
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
#define MAXN 100005

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

int nivel[MAXN], low[MAXN];
int n,m,cbc;

void scoate(int nod, int urm)
{
    while(st.top() != urm)
    {
        rasp[cbc].push_back( st.top() );
        st.pop();
    }
    st.pop();
    rasp[cbc].push_back(nod);
    rasp[cbc].push_back(urm);
}
void dfs(int nod, int k)
{
    nivel[nod]=low[nod]=k;

    for(int i=0; i<graf[nod].size(); i++)
    {
        int urm = graf[nod][i];
        if(!nivel[urm])
        {
            st.push(urm);
            dfs(urm,k+1);
            low[nod]=min(low[nod], low[urm]);
            if(low[urm] >= nivel[nod])
            {
                cbc++;
                scoate(nod,urm);
            }
        }
        else
            low[nod]=min(low[nod], nivel[urm]);
    }
}
int main()
{
    int n,m,i,j,x,y;
    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++)
    {
        sort(rasp[i].begin(),rasp[i].end());
        for(j=0; j<rasp[i].size(); j++)
            cout<<rasp[i][j]<<" ";
        cout<<"\n";
    }
    return 0;
}