Cod sursa(job #2002182)

Utilizator Bodo171Bogdan Pop Bodo171 Data 18 iulie 2017 22:18:18
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
const int nmax=100005;
vector< pair<int,int> > v[nmax];
vector<int> l[2*nmax];
int st[2*nmax],x[2*nmax],y[2*nmax],lev[nmax],low[nmax],afis[nmax];
int n,m,u,comp,i,j;
void mark(int A)
{
    int P=st[u];
    u--;
    if(P!=0)l[comp].push_back(x[P]);
    if(P!=0)l[comp].push_back(y[P]);
    if(P==A)
        return;
    mark(A);
}
void dfs(int x)
{
    int nod=0;
    for(int i=0;i<v[x].size();i++)
    {
        nod=v[x][i].first;
        if(!lev[nod])
        {
            lev[nod]=lev[x]+1;
            u++;st[u]=v[x][i].second;
            dfs(nod);
            if(low[nod]>=lev[x])
            {
                comp++;
                mark(v[x][i].second);
            }
            if(low[nod]<low[x])
                low[x]=low[nod];
        }
        else
        {
           low[x]=min(low[x],lev[nod]);
        }
    }
}
int main()
{
    ifstream f("biconex.in");
    ofstream g("biconex.out");
    f>>n>>m;
    for(i=1;i<=n;i++)
        low[i]=(1<<30);
    for(i=1;i<=m;i++)
    {
        f>>x[i]>>y[i];
        v[x[i]].push_back({y[i],i});
        v[y[i]].push_back({x[i],i});
    }
    lev[1]=1;
    dfs(1);
    mark(0);
    g<<comp<<'\n';
    for(i=1;i<=comp;i++)
    {
        for(j=0;j<l[i].size();j++)
        {
            if(!afis[l[i][j]])
                g<<l[i][j]<<' ';
            afis[l[i][j]]=1;
        }
        for(j=0;j<l[i].size();j++)
            afis[l[i][j]]=0;
        g<<'\n';
    }
    return 0;
}