Cod sursa(job #2371154)

Utilizator Bodo171Bogdan Pop Bodo171 Data 6 martie 2019 16:16:33
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb

#include <iostream>

#include <fstream>

#include <vector>

using namespace std;

const int nmax=100005;

const int mmax=200005;

vector< pair<int,int> > v[nmax];

vector<int> l[mmax];

int lev[nmax],low[nmax],ap[nmax];

int st[mmax],a[mmax],b[mmax];

int n,m,i,j,u,bcc;

void mark(int P)

{

    l[bcc].push_back(a[st[u]]);

    l[bcc].push_back(b[st[u]]);

    if(st[u]!=P) {u--;mark(P);}

    else u--;

}

void dfs(int x)

{

    int nod,et;

    for(int i=0;i<v[x].size();i++)

    {

        nod=v[x][i].first;et=v[x][i].second;

        if(!lev[nod])

        {

            st[++u]=et;

            lev[nod]=lev[x]+1;

            dfs(nod);

            if(low[nod]>=lev[x])

            {

                bcc++;

                mark(et);

            }

            if(low[nod]<low[x])

                low[x]=low[nod];

        }

        else

        {

            if(lev[nod]<low[x])

                low[x]=lev[nod];

        }

    }

}

int main()

{

    ifstream f("biconex.in");

    ofstream g("biconex.out");

    f>>n>>m;

    for(i=1;i<=m;i++)

    {

        f>>a[i]>>b[i];

        v[a[i]].push_back({b[i],i});

        v[b[i]].push_back({a[i],i});

    }

    lev[1]=1;

    for(i=1;i<=n;i++)

        low[i]=(1<<30);

    dfs(1);

    g<<bcc<<'\n';

    for(i=1;i<=bcc;i++)

    {

        for(j=0;j<l[i].size();j++)

        {

            if(!ap[l[i][j]])

                ap[l[i][j]]=1,g<<l[i][j]<<' ';

        }

        for(j=0;j<l[i].size();j++)

            ap[l[i][j]]=0;

        g<<'\n';

    }

    return 0;

}