Cod sursa(job #3192356)

Utilizator Samoila_AlexandruSamoilaAlexandru Samoila_Alexandru Data 12 ianuarie 2024 12:44:41
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.78 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

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

const int nMax=(int)1e5+5;

int op, n, m, x, y, dfn[nMax], low[nMax], nrCompBi;
vector<int> g[nMax];
vector<vector<int>> muchii;
stack<pair<int, int>> s;

void afis(int nod, int k)
{
    nrCompBi++;
    int auxFirst, auxSecond;
    vector<int> aux;
    do {
        auxFirst=s.top().first, auxSecond=s.top().second;
        s.pop();

        aux.push_back(auxFirst);
        aux.push_back(auxSecond);
    }
    while(auxFirst != nod || auxSecond != k);

    muchii.push_back(aux);
}

void biconex(int nod, int tata, int nr)
{
    dfn[nod]=low[nod]=nr;

    for(auto k: g[nod])
    {
        if(k == tata)
            continue;

        if(dfn[k] == -1)
        {
            s.push({nod, k});
            biconex(k, nod, nr + 1);
            low[nod]=min(low[nod], low[k]);
            if(low[k] >= dfn[nod])
                afis(nod, k);
        }
        else low[nod]=min(low[nod], dfn[k]);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);

    fin>>n>>m;
    for(int i=0; i<m; i++)
    {
        fin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    for(int i=1; i<=n; i++)
        dfn[i]=low[i]=-1;

    biconex(1, 0, 0);

    fout<<nrCompBi<<'\n'; //muchii.size()

    for(int i=0; i<muchii.size(); i++)
    {
        sort(muchii[i].begin(), muchii[i].end());
        muchii[i].erase(unique(muchii[i].begin(), muchii[i].end()), muchii[i].end());
        for(int j=0; j<muchii[i].size(); j++)
            fout<<muchii[i][j]<<' ';
        fout<<'\n';
    }

    fin.close(); fout.close();

    return 0;
}