Cod sursa(job #2371143)

Utilizator Bodo171Bogdan Pop Bodo171 Data 6 martie 2019 16:10:37
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=100005;
const int mmax=2*nmax;
vector< pair<int,int> > v[nmax];
vector<int> li[mmax];
int st[mmax],unu[mmax],doi[mmax];
int low[nmax],lev[nmax];
int n,m,bcc,i,j,u,a,b;
void mark(int et)
{
    li[bcc].push_back(unu[st[u]]);
    li[bcc].push_back(doi[st[u]]);
    u--;
    if(et!=st[u+1]) mark(et);
}
void dfs(int x)
{
    int nod=0;
    low[x]=n+1;
    for(int i=0;i<v[x].size();i++)
    {
        nod=v[x][i].first;
        if(!lev[nod])
        {
            lev[nod]=lev[x]+1;
            st[++u]=v[x][i].second;
            dfs(v[x][i].first);
            if(low[nod]>=lev[x])
            {
                bcc++;
                mark(v[x][i].second);
            }
            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>>b;
        v[a].push_back({b,i});
        v[b].push_back({a,i});
        unu[i]=a,doi[i]=b;
    }
    for(int s=1;s<=n;s++)
        if(!lev[s])
    {
        lev[s]=1;
        dfs(s);
    }
    g<<bcc<<'\n';
    for(i=1;i<=bcc;i++)
    {
        for(j=0;j<li[i].size();j++)
            if(lev[li[i][j]])
               g<<li[i][j]<<' ',lev[li[i][j]]=0;
        for(j=0;j<li[i].size();j++)
            lev[li[i][j]]=1;
        g<<'\n';
    }
    return 0;
}