Cod sursa(job #3342918)

Utilizator AnSeDraAndrei Sebastian Dragulescu AnSeDra Data 26 februarie 2026 09:58:58
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.03 kb
#include <fstream>
#include <vector>
#include <set>
#include <stack>

using namespace std;

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

const int Nmax = 200005;

struct nod{
    int timp_initial, timp_atins, nr_componenta;
    vector<int> vecini;
};

int n, m, timp, nr_componenta;
nod graf[Nmax];
stack<pair<int, int>> st;
set<int> componente[Nmax];

void citire(){
    int nod1, nod2;

    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        fin >> nod1 >> nod2;
        graf[nod1].vecini.push_back(nod2);
        graf[nod2].vecini.push_back(nod1);
    }
}

void dfs_tarjan(int nod, int parinte){
    graf[nod].timp_initial = graf[nod].timp_atins = ++timp;

    for(int vecin : graf[nod].vecini){
        if(!graf[vecin].timp_initial){
            st.push({nod, vecin});
            dfs_tarjan(vecin, nod);
            graf[nod].timp_atins = min(graf[nod].timp_atins, graf[vecin].timp_atins);

            if(graf[vecin].timp_atins >= graf[nod].timp_initial){
                nr_componenta++;

                while(st.top().first != nod || st.top().second != vecin){
                    componente[nr_componenta].insert(st.top().first);
                    componente[nr_componenta].insert(st.top().second);
                    st.pop();
                }

                componente[nr_componenta].insert(nod);
                componente[nr_componenta].insert(vecin);
                st.pop();
            }
        }
        else if(vecin != parinte){
            if(graf[vecin].timp_initial < graf[nod].timp_initial){
                graf[nod].timp_atins = min(graf[nod].timp_atins, graf[vecin].timp_initial);
                st.push({nod,vecin});
            }
        }
    }
}

void afisare(){
    fout << nr_componenta << '\n';
    for(int i = 1; i <= nr_componenta; i++){
        for(int nod : componente[i]){
            fout << nod << ' ';
        }
        fout << '\n';
    }
}

int main(){
    citire();

    dfs_tarjan(1, 0);
    afisare();

    return 0;
}