Cod sursa(job #1880608)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 15 februarie 2017 20:39:04
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <cstdio>
#include <vector>
#define Nmax 100001
using namespace std;

ofstream g("biconex.out");

int n,bst[Nmax],nr,m,in[Nmax];
vector<int> V[Nmax],st,rez[Nmax];

void dfs(int nod,int ant)
{
    st.push_back(nod);


    for (int i=0;i<V[nod].size();i++)
    {
        if (!bst[V[nod][i]])
        {
            int k = st.size();
            bst[V[nod][i]] = in[nod]+1;
            in[V[nod][i]] = in[nod]+1;
            dfs(V[nod][i],nod);
            bst[nod] = min(bst[V[nod][i]],bst[nod]);
            if (bst[V[nod][i]]>=in[nod])
            {
                nr++;
                while (st.size()>k)
                {
                    rez[nr].push_back(st.back());
                    st.pop_back();
                }
                rez[nr].push_back(st.back());
            }
        }
        else
        {
            bst[nod] = min(in[V[nod][i]],bst[nod]);
        }
    }
}

int main()
{
    freopen("biconex.in","r",stdin);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        V[x].push_back(y);
        V[y].push_back(x);
    }

    bst[1] = in[1] = 1;
    dfs(1,0);

    g<<nr<<'\n';
    for (int i=1;i<=nr;i++)
    {
        for (int j=0;j<rez[i].size();j++)
            g<<rez[i][j]<<' ';
        g<<'\n';
    }
    return 0;
}