Cod sursa(job #2121066)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 3 februarie 2018 11:36:45
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <bitset>
#define pb push_back

using namespace std;
vector <int> g[100003], sol[100003];
vector <pair<int,int>> v;
int n,m,a,b,k;
bitset <100003> uz;
int niv[100003], llk[100003];
void dfs(int ln, int pre)
{
    if(pre!=-1)
        niv[ln]=niv[pre]+1;
    else
        niv[ln]=1;
    llk[ln]=niv[ln];
    for(int i:g[ln])
    {
        if(!niv[i])
        {
            v.pb({ln,i});
            dfs(i,ln);
            llk[ln]=min(llk[ln],llk[i]);
            if(llk[i]>=niv[ln])
            {
                uz.reset();
                while(v.size())
                {
                    pair<int,int> l=v.back();
                    v.pop_back();
                    if(!uz[l.first])
                        sol[k].push_back(l.first), uz[l.first]=1;
                    if(!uz[l.second])
                        sol[k].push_back(l.second), uz[l.second]=1;
                    if(l.first==ln && l.second==i)
                        break;
                }
                ++k;
            }
        }
        else if(i!=pre)
        {
            llk[ln]=min(llk[ln],niv[i]);
        }

    }
}
int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d %d", &n,&m);
    for(int i=0;i<m;++i)
    {
        scanf("\n%d %d", &a,&b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i=1;i<=n;++i)
    {
        if(!niv[i])
        {
            dfs(i,-1);
        }
    }
    cout<<k<<"\n";
    for(int i=0;i<k;++i)
    {
        for(int j:sol[i])
            cout<<j<<" ";
        cout<<"\n";
    }
    return 0;
}