Cod sursa(job #1233431)

Utilizator thewildnathNathan Wildenberg thewildnath Data 25 septembrie 2014 12:42:54
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;

#define NMAX 100002
#define MMAX 200002

int n, m;
int niv[NMAX], nivmin[NMAX];

vector<vector<int> > sol;
vector<int> v[NMAX], aux;
stack<int> st;

void adaug_sol(int nod)
{
    aux.clear();
    while(true)
    {
        aux.push_back(st.top());
        if(st.top()==nod)
            break;
        st.pop();
    }

    sol.push_back(aux);
}

void dfs(int nod, int t, int nv)
{
    int fiu;

    niv[nod]=nivmin[nod]=nv;
    st.push(nod);

    for(int i=0; i<v[nod].size(); ++i)
    {
        fiu=v[nod][i];

        if(fiu==t)
            continue;

        if(!niv[fiu])
        {
            dfs(fiu, nod, nv+1);

            if(nivmin[fiu]>=niv[nod])
                adaug_sol(nod);

            nivmin[nod]=min(nivmin[nod], nivmin[fiu]);
        }else
            nivmin[nod]=min(nivmin[nod], niv[fiu]);
    }
}

int main()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);

    int x, y;

    scanf("%d%d", &n, &m);

    for(int i=1; i<=m; ++i)
    {
        scanf("%d%d", &x, &y);

        v[x].push_back(y);
        v[y].push_back(x);
    }

    dfs(1, 0, 1);

    printf("%d\n", sol.size());
    for(int i=0; i<sol.size(); ++i)
    {
        sort(sol[i].begin(), sol[i].end());
        for(int j=0; j<sol[i].size(); ++j)
            printf("%d ", sol[i][j]);
        printf("\n");
    }

    return 0;
}