Cod sursa(job #3269790)

Utilizator Alex_BerbescuBerbescu Alexandru Alex_Berbescu Data 20 ianuarie 2025 18:09:06
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#pragma GCC optimize("O3")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
const int dim = 1e5 + 55;
vector<int>graph[dim];
int n, m;
int level[dim], v[dim];
vector<int>sol;
vector<vector<int> >bic;
stack<pair<int, int> >stiva;

void add(pair<int, int>nod)
{
    pair<int, int>nd;
    do
    {
        nd = stiva.top();
        stiva.pop();
        sol.push_back(nd.first);
        sol.push_back(nd.second);
    }while(nd != nod);
    sort(sol.begin(), sol.end());
    sol.erase(unique(sol.begin(), sol.end()), sol.end());
    bic.push_back(sol);
    sol.clear();

}
void biconex(int nod = 1, int tata = 0)
{
    v[nod] = level[nod];
    for(auto it: graph[nod])
    {
        if(!level[it])
        {
            level[it] = level[nod] + 1;
            stiva.push({nod, it});
            biconex(it, nod);
            if(v[it] >= level[nod])
            {
                add({nod, it});
            }
        }
    }
    bool ok = false;
    for(auto it: graph[nod])
    {
        if(it == nod && !ok)
            ok = true;
        else
            v[nod] = min(v[nod], v[it]);
    }
}


ifstream fin("biconex.in");
ofstream fout("biconex.out");
int32_t main(int argc, char * argv[])
{
    fin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        int x, y;
        fin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    level[1] = 1;
    biconex();
    fout << bic.size() << '\n';
    for(int i = 0; i < bic.size(); ++i, fout << '\n')
    {
        for(int j = 0; j < bic[i].size(); ++j)
            fout << bic[i][j] << " ";
    }
    return 0;
}