Cod sursa(job #3347663)

Utilizator Commander_XDunel Stefan-Octavian Commander_X Data 17 martie 2026 18:37:33
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.26 kb
#include <fstream>
#include <vector>
#include <set>
#include <stack>

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

using namespace std;

const int oo = 0x3f3f3f3f;

vector<vector<int>> G;
vector<set<int>> BCC;
vector<int> dfn,low,Art;
stack<pair<int,int>> S;
int N,M,nr_fii = 0,num = 0,nrBCC = 0,start;

void read()
{
    fin >> N >> M;
    G.resize(N+1);
    BCC.resize(N+1);
    dfn.resize(N+1,-1);
    low.resize(N+1,oo);
    Art.resize(N+1,0);

    int x,y;
    for(int i = 1; i <= M; ++i)
    {
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}
void Build_BCC(int x,int y)
{
    ++nrBCC;
    pair<int,int> crt;
    do
    {
        crt.first = S.top().first;
        crt.second = S.top().second;
        S.pop();
        BCC[nrBCC].insert(crt.first);
        BCC[nrBCC].insert(crt.second);
    }while(crt.first != x || crt.second != y);
}
void DFSBCC(int nod_s,int nod_t)
{
    dfn[nod_s] = low[nod_s] = ++num;
    for(auto vecin : G[nod_s])
    {
        if(vecin != nod_t && dfn[vecin] < dfn[nod_s])
            S.push({vecin,nod_s});
        if(dfn[vecin] == -1)
        {
            if(nod_s == start)
                nr_fii++;
            DFSBCC(vecin,nod_s);
            low[nod_s] = min(low[nod_s],low[vecin]);
            if(low[vecin] >= dfn[nod_s])
            {
                if(nod_s != start)
                    Art[nod_s] = 1;
                Build_BCC(vecin,nod_s);
            }
        }
        else
            if(vecin != nod_t)
                low[nod_s] = min(low[nod_s],low[vecin]);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    fin.tie(0);

    read();
    start = 1;
    DFSBCC(1,-1);
    if(nr_fii > 1)
        Art[start] = 1;

    if(nrBCC == 0)
    {
        ++nrBCC;
        pair<int,int> crt;
        while(!S.empty())
        {
            crt.first = S.top().first;
            crt.second = S.top().second;
            S.pop();
            BCC[nrBCC].insert(crt.first);
            BCC[nrBCC].insert(crt.second);
        }
    }

    fout << nrBCC << '\n';
    for(int i = 1; i <= nrBCC; ++i)
    {
        for(auto elem : BCC[i])
            fout << elem << ' ';
        fout << '\n';
    }
}