Cod sursa(job #3373071)

Utilizator vladl02Lungu Vladislav vladl02 Data 6 noiembrie 2026 01:16:22
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.42 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;

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

int n, m;

vector<int> viz;
stack<pair<int, int>> muchii;
vector<int> level;
vector<int> min_level;
vector<vector<int>> adj;
vector<vector<int>> componente;

vector<int> noduri;
vector<int> marcaj;
int id_componenta = 0;


void DFS(int x, int parent){
    viz[x] = 1;
    level[x] = level[parent] + 1;
    min_level[x] = level[x];

    for (auto i: adj[x]){
        if (i == parent) continue;

        if (!viz[i]){
            muchii.push({x, i});

            DFS(i, x);

            min_level[x] = min(min_level[x], min_level[i]);

            if (min_level[i] >= level[x]){
                noduri.clear();
                id_componenta++;

                while (true)
                {
                    auto muchie = muchii.top();
                    muchii.pop();


                    int a = muchie.first;
                    int b = muchie.second;

                    if (marcaj[a] != id_componenta) {
                        noduri.push_back(a);
                        marcaj[a] = id_componenta;
                    }
                    
                    if (marcaj[b] != id_componenta) {
                        noduri.push_back(b);
                        marcaj[b] = id_componenta;
                    }
                    
                    if (a == x && b == i) break;
                }
                componente.emplace_back(vector<int>(noduri.begin(), noduri.end()));
                
            }

        } else if (level[i] < level[x]){
            muchii.push({x, i});
            min_level[x] = min(level[i], min_level[x]);
        }
        
    }

}


int main(){

    file_in >> n >> m;

    viz.resize(n+1, 0);
    adj.resize(n+1);
    level.resize(n+1, 0);
    min_level.resize(n+1, 0);
    marcaj.resize(n + 1, 0);
    
    for (int i=1; i<=m; i++){
        int x, y;
        file_in >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    for (int i = 1; i <= n; i++) {
        if (!viz[i]) {
            DFS(i, 0);
        }
    }

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

    for (auto &comp : componente) {
        for (int x : comp) {
            file_out << x << " ";
        }
        file_out << '\n';
    }
    

    return 0;
}