Cod sursa(job #2796564)

Utilizator Tache_RoxanaTache Roxana Tache_Roxana Data 8 noiembrie 2021 14:26:50
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>

using namespace std;

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

const int maxim = 100002;

int nma[maxim], nivel[maxim], vizitate[maxim];
int n, m, nrSolutii;
vector<int> a[maxim], solutie[maxim];
stack<int> stiva;

void citireGraf(){
    in >> n >> m;
    int x, y;
    for(int i = 1; i <= m; i++){
        in >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);

    }
}

void dfs(int nod, int tata) {
    vizitate[nod] = 1;
    nma[nod] = nivel[nod] = nivel[tata] + 1;
    stiva.push(nod);

    for (auto x: a[nod]) {
        if (x != tata){
            if (vizitate[x])
                nma[nod] = min(nma[nod], nivel[x]);
            else{
                dfs(x, nod);
                nma[nod] = min(nma[nod], nma[x]);

                if (nma[x] >= nivel[nod]) {
                    nrSolutii++;
                    while (stiva.top() != x) {
                        solutie[nrSolutii].push_back(stiva.top());
                        stiva.pop();
                    }
                    solutie[nrSolutii].push_back(x);
                    stiva.pop();
                    solutie[nrSolutii].push_back(nod);
                }
            }
        }
    }
}

int main() {
    citireGraf();

    for (int i = 1; i <= n; i++)
        if (vizitate[i] == 0)
            dfs(i, 0);
    out << nrSolutii << "\n";
    for (int i = 1; i <= nrSolutii; i++) {
        for (auto j: solutie[i])
            out << j << " ";
        out << "\n";
    }
    return 0;
}