Cod sursa(job #3204853)

Utilizator AlfexAlex Florea Alfex Data 17 februarie 2024 19:26:16
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <bits/stdc++.h>

#define NMAX 100001

using namespace std;

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

int N, M, nivel[NMAX], nma[NMAX], k;
vector<int> vecini[NMAX];
stack<int> s;
vector< pair<int, int> > mc;
vector<int> art;
vector<int> compConex[NMAX];
bool viz[NMAX];

void dfs(int nod, int tata){
    nivel[nod] = nivel[tata] + 1;
    nma[nod] = nivel[nod];
    viz[nod] = true;

    bool pctArt = false;
    s.push(nod);
    for(auto vecin : vecini[nod]){
        if(viz[vecin] && !(tata == vecin))
            nma[nod] = min(nma[nod], nivel[vecin]);
        else if(!viz[vecin]){
            dfs(vecin, nod);
            nma[nod] = min(nma[nod], nma[vecin]);
            if(nivel[nod] <= nma[vecin] && nod != 1){
                pctArt = true;
            }
            if(nivel[nod] < nma[vecin]){
                mc.push_back(make_pair(nod, vecin));
            }
            if(nivel[nod] <= nma[vecin]){
                k ++;
                while(s.top() != vecin){
                    compConex[k].push_back(s.top());
                    s.pop();
                }
                compConex[k].push_back(s.top());
                s.pop();
                compConex[k].push_back(nod);
            }
        }
    }
    if(pctArt == true){
        art.push_back(nod);
    }
}

int main()
{
    f >> N >> M;
    for(int i = 1; i <= M; i ++){
        int x, y;
        f >> x >> y;
        vecini[x].push_back(y);
        vecini[y].push_back(x);
    }
    dfs(1, 0);
    g << k << '\n';
    for(int i = 1; i <= k; i ++){
        for(auto el = compConex[i].rbegin(); el < compConex[i].rend(); el ++){
            g << *el << " ";
        }
        g << '\n';
    }
    return 0;
}