Cod sursa(job #2647935)

Utilizator roberttrutaTruta Robert roberttruta Data 7 septembrie 2020 14:50:48
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include <fstream>
#include <vector>
using namespace std;
vector <int> v[200005],afis[200005];
int n,m,a,b,lv[200005],stramos[200005],viz[200005],tata[200005],t,r,j;
const int inf=20000000;
struct vct
{
    int x,y;
}muchie[200005];
///lv= nivelul nodului in arbore
///stramos= cel mai mic nivel la care poate urca un nod folosind o muchie de intoarcere
///muchie= gen stiva cu muchii in ordinea parcurgerii DFS
inline void componenta(int x, int y)
{///se elimina toate muchiile din stiva pana la muchia critica inclusiv
///muchiile eliminate formeaza o componenta biconexa
    r++;
    while(muchie[t].y!=y)
    {
        afis[r].push_back(muchie[t].x);
        t--;
    }
    afis[r].push_back(muchie[t].x);
    afis[r].push_back(muchie[t].y);
    t--;
}
inline void dfs(int start, int vecin, int bk)
{
    int i;
    viz[start]=1; lv[start]=lv[bk]+1; tata[start]=bk;
    muchie[++t].x=start; muchie[t].y=bk;
    for(i=0;i<v[start].size();i++)
    {
        vecin=v[start][i];
        if(!viz[vecin])
        {
               dfs(vecin,0,start);
               if(stramos[start]>stramos[vecin])
                stramos[start]=stramos[vecin];///tata nu poate avea stramos mai mare decat fii
                if(stramos[vecin]>=lv[start])
                    componenta(vecin,start);///am gasit fiu care nu poate urca mai sus decat tata
                    ///(tata aici e nod de articulatie, iar muchia start-vecin e critica)
        }
        else
            if(stramos[start]>lv[vecin] && vecin!=bk)
            stramos[start]=lv[vecin];
    }
}
int main()
{
    ifstream f("biconex.in");
    ofstream g("biconex.out");
int i;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(i=1;i<=n;i++)
    stramos[i]=inf;
    dfs(1,0,0);

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

    return 0;
}