Cod sursa(job #2796400)

Utilizator HatersMcCristian Ioan HatersMc Data 7 noiembrie 2021 23:46:02
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb

#include <bits/stdc++.h>
#define DIM_MAX  100005
using namespace std;

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

vector<bool> v(DIM_MAX);
vector<int>  v1(DIM_MAX), v2(DIM_MAX), v3(DIM_MAX);
vector<vector<int>> mat(DIM_MAX);
vector<vector<int> > comp;
deque<pair<int, int> > stiv;

void adaug_comp(int x, int y) {
    int a, b;
    vector<int> row;
    vector<bool> added(DIM_MAX);
    while(!stiv.empty() && (a!=x || b!=y)) // trecem prin striva si adaugam e un nou row elementele comp biconexe
    {
        a = stiv.back().first;
        b = stiv.back().second;
        stiv.pop_back();
        if(!added[a]){
        row.push_back(a);
        added[a]=true;}
        if(!added[b])
        {row.push_back(b);
        added[b]=true;}
    }
    sort(row.begin(), row.end());
    comp.push_back(row);
}

void dfs(int x) {
    v[x] = true;
    v2[x] = v1[x] = v2[v3[x]]+1;
    for(auto a: mat[x]) { // trecem prin elementele adiacente nodului
        if(!v[a]) { // daca nu e vizitat
            stiv.push_back({x, a});
            v3[a] = x;
            dfs(a);

            if(v1[a] >= v2[x])
                adaug_comp(x, a);

            v1[x] = min(v1[x], v1[a]);
        } else if(a != v3[x]) // daca nodul adiacent lui x nu este nodul precendent din care vine x
            v1[x] = min(v1[x], v2[a]);
    }
}

int main() {
    int n,m;
    f >> n >> m;
    for(int i = 0 ; i < m ; ++i){
        int a, b;
        f >> a >> b;
        mat[a].push_back(b);
        mat[b].push_back(a);
    }
    dfs(1);
    g << comp.size() << '\n';
    for(auto a: comp) {
        for(auto b:a)
                g << b << ' ';
        g << '\n';
    }
}