Cod sursa(job #2873050)

Utilizator k2y201342asdfadfsafsd k2y20 Data 18 martie 2022 15:41:38
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <bits/stdc++.h>
using namespace std;

ifstream in("biconex.in");
ofstream out("biconex.out");

const int N=1e5;
struct graf
{
    vector<int> v;
}la[N+5];
vector<vector<int> >biconex;

int nivel[N+5],nma[N+5],nrBiconex;
stack <int> stk;

void dfs(int rad,int nod,int tata)
{
    if(tata == -1) nma[nod]=nivel[nod]=1;
    else nma[nod]=nivel[nod]=nivel[tata]+1;
    stk.push(nod);

    for(int i=0;i<la[nod].v.size();i++)
    {
        int to=la[nod].v[i];
        if(!nivel[to])
        {
            dfs(rad,to,nod);
            nma[nod]=min(nma[nod],nma[to]);

            if( nivel[nod] <= nma[to])
            {
                nrBiconex++;
                vector <int> aux;
                while(stk.top()!=to)
                {
                    aux.push_back(stk.top());
                    stk.pop();
                }
                aux.push_back(stk.top());
                stk.pop();
                aux.push_back(nod);
                biconex.push_back(aux);
            }
        }
        else nma[nod]=min(nma[nod],nivel[to]);
    }

}

int main()
{
    int n,m;
    in>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x,y;
        in>>x>>y;
        la[x].v.push_back(y);
        la[y].v.push_back(x);
    }

    for(int i=1;i<=n;i++)
        if(!nivel[i]) dfs(i,i,-1);
    out<<nrBiconex<<'\n';

    for(int i=0;i<biconex.size();i++)
    {
        for(int j=0;j<biconex[i].size();j++)
            out<<biconex[i][j]<<' ';
        out<<'\n';
    }
}