Cod sursa(job #3030819)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 17 martie 2023 21:45:43
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.86 kb
#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
ifstream in("biconex.in");
ofstream out("biconex.out");
#define cin in
#define cout out
#endif // LOCAL

const int NMAX =1e5 + 7;
int depth[NMAX], low[NMAX], visited[NMAX], parent[NMAX];
vector<int> g[NMAX];

vector<int> ap;
vector<int> stiva;
vector<vector<int>> bicomp;

void dfs(int node, int d) {
    depth[node] = d;
    low[node] = d;

    int children = 0;

    bool is_articulation = false;
    stiva.push_back(node);

    for(auto vec : g[node]) {
        if(depth[vec] == 0) {
            parent[vec] = node;
            dfs(vec, d + 1);
            children += 1;

            if(low[vec] >= depth[node]) {
                is_articulation = true;

                vector<int> comp;
                while(!stiva.empty() && stiva.back() != vec) {
                    comp.push_back(stiva.back());
                    stiva.pop_back();
                }

                stiva.pop_back();
                comp.push_back(vec);
                comp.push_back(node);
                bicomp.push_back(comp);
            }

            low[node] = min(low[node], low[vec]);
        }
        else if(vec != parent[node]) {
            low[node] = min(low[node], depth[vec]);
        }
    }

    if(parent[node] != 0 && is_articulation) {
        ap.push_back(node);
    }
    if(parent[node] == 0 && children > 1) {
        ap.push_back(node);
    }
}

int main()
{
    int n, m; cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int x, y; cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

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

    cout << bicomp.size() << '\n';
    for(auto e : bicomp) {
        for(auto ee : e) cout << ee << " ";
        cout << '\n';
    }

    return 0;
}