Cod sursa(job #1912479)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 8 martie 2017 09:13:42
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <fstream>
#include <cstdio>
#include <vector>
#define inf 1e9
#define Nmax 100001
using namespace std;

ofstream g("biconex.out");

int n,m,r,inSt[Nmax];
bool uz[Nmax];
vector<int> V[Nmax],st;
vector<int> rez[Nmax];



int dfs(int nod)
{
    int poz = st.size()+1,mn = st.size()+1,mn2 = inf;
    uz[nod] = 1;
    st.push_back(nod);
    inSt[nod] = st.size();
    for (int i=0;i<V[nod].size();i++)
    {
        if (!uz[V[nod][i]])
        {
            int d = dfs(V[nod][i]);
            mn = min(mn,d);
            if (d==poz)
            {
                r++;
                int i = st.size()-1;
                while (i>=poz-1)
                {
                    rez[r].push_back(st[i]);
                    i--;
                    if (i!=poz-1)
                    {
                        inSt[st.back()] = 0;
                        st.pop_back();
                    }
                }
            }
           /* else if (d==poz+1)
            {
                r++;
                rez[r].push_back(st.back());
                st.pop_back();
                rez[r].push_back(st.back());
            }*/
        }
        else if (inSt[V[nod][i]])
            mn2 = min(inSt[V[nod][i]],mn2);
    }
    return min(mn2,mn);
}

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);
    }

    dfs(1);

    g<<r<<'\n';

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


    return 0;
}