Cod sursa(job #3374189)

Utilizator erikaantonescuAntonescu Erika erikaantonescu Data 8 noiembrie 2026 20:12:01
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.04 kb

#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

const int nmax = 100001;

vector<int> graf[nmax];
int tin[nmax], low[nmax], timer = 0;
int marcat[nmax];

vector<pair<int, int>> muchii;
vector<vector<int>> componente;

void dfs(int nod, int tata){
    tin[nod] = low[nod] = ++timer;

    for (int vecin : graf[nod]){
        if (vecin == tata)
            continue;

        if (tin[vecin] == 0){

            muchii.push_back({nod, vecin});
            dfs(vecin, nod);
            low[nod] = min(low[nod], low[vecin]);

            if (low[vecin] >= tin[nod]){
                vector<int> componenta;
                int nr = componente.size() + 1;

                while (true){
                    int x = muchii.back().first;
                    int y = muchii.back().second;
                    muchii.pop_back();

                    if (marcat[x] != nr){
                        componenta.push_back(x);
                        marcat[x] = nr;
                    }

                    if (marcat[y] != nr){
                        componenta.push_back(y);
                        marcat[y] = nr;
                    }

                    if (x == nod && y == vecin)
                        break;
                }

                componente.push_back(componenta);
            }
        }
        else if (tin[vecin] < tin[nod]){
            muchii.push_back({nod, vecin});
            low[nod] = min(low[nod], tin[vecin]);
        }
    }
}

int main(){
    int n, m;
    fin >> n >> m;

    for (int i = 0; i < m; i++){
        int x, y;
        fin >> x >> y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }

    for (int i = 1; i <= n; i++)
        if (tin[i] == 0)
            dfs(i, 0);

    fout << componente.size() << '\n';

    for (vector<int> c : componente){
        for (int nod : c)
            fout << nod << " ";
        fout << '\n';
    }

    return 0;
}