Cod sursa(job #1689552)

Utilizator sorynsooSorin Soo sorynsoo Data 14 aprilie 2016 12:42:28
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

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

vector<int> graf[MAXN], cbc[MAXN];
stack<int> st;
int nivel[MAXN], low[MAXN];
int n, m, nrCbc;


void scoate(int stg, int fin)
{
    while(st.top() != fin)
    {
        cbc[nrCbc].push_back( st.top() );
        st.pop();
    }
    st.pop();
    cbc[nrCbc].push_back( stg );
    cbc[nrCbc].push_back( fin );
}

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])
            {
                nrCbc++;
                scoate(nod,urm);
            }
        }
        else
            low[nod] = min(low[nod], nivel[urm]);
    }
    
}
int main()
{
    int 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<<nrCbc<<"\n";
    for(i=1; i<=nrCbc; i++)
    {
        sort( cbc[i].begin(), cbc[i].end() );
        for(j=0; j<cbc[i].size(); j++)
            cout<<cbc[i][j]<<" ";
        cout<<"\n";
    }
    return 0;
}