Cod sursa(job #2796236)

Utilizator Alex18maiAlex Enache Alex18mai Data 7 noiembrie 2021 19:18:48
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.12 kb
/*
Alexandru Enache
Grupa 252
*/

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


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


class Graph{

private:

    int m_nodes;
    vector < vector < int > > m_gr;

    void dfs(int node, vector < bool > &used){
        used[node] = true;
        for (auto &x: m_gr[node]){
            if (!used[x]){
                dfs(x, used);
            }
        }
    }

    void dfs_biconexe (int nod , int dad, vector < int > &lv, vector < int > &MIN, stack < int > &s, vector < vector < int > > &ans){
        lv[nod] = lv[dad]+1;
        MIN[nod] = lv[nod];
        s.push(nod);
        for (auto &x : m_gr[nod]){
            if (lv[x]){
                if (x != dad){
                    MIN[nod] = min(MIN[nod] , lv[x]);
                }
            }
            else{
                dfs_biconexe(x , nod, lv, MIN, s, ans);
                MIN[nod] = min(MIN[nod] , MIN[x]);
                if (MIN[x] >= lv[nod]){
                    vector < int > aux;
                    while (s.top() != x){
                        aux.push_back(s.top());
                        s.pop();
                    }
                    aux.push_back(x);
                    s.pop();
                    aux.push_back(nod);
                    ans.push_back(aux);
                }
            }
        }
    }

public:

    Graph(int nodes, vector < vector < int > > &gr){
        m_nodes = nodes;
        m_gr = gr;
    }

    vector < int > bfs(int start){
        queue < int > q;
        vector < int > dist(m_nodes + 1, -1);

        dist[start] = 0;
        q.push(start);

        while (!q.empty()){
            int now = q.front();
            q.pop();

            for (auto &x : m_gr[now]){
                if (dist[x] == -1){
                    dist[x] = dist[now] + 1;
                    q.push(x);
                }
            }
        }

        return dist;
    }

    int comp_conexe(){

        int cont = 0;
        vector < bool > used(m_nodes + 1, false);
        for (int i=1; i<=m_nodes; i++){
            if (!used[i]){
                dfs(i, used);
                cont++;
            }
        }

        return cont;
    }

    vector < vector < int > > comp_biconexe(){

        vector < vector < int > > ans;

        vector < int > lv (m_nodes + 1, 0);
        vector < int > MIN (m_nodes + 1, 0);
        stack < int > s;

        for (int i=1; i<=m_nodes; i++){
            if (!lv[i]){
                dfs_biconexe(i , 0, lv, MIN, s, ans);
            }
        }

        return ans;
    }

};


void solve() {

    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n, m;
    fin>>n>>m;

    vector < vector < int > > gr(n+1);

    for (int i=1; i<=m; i++){
        int a, b;
        fin>>a>>b;
        gr[a].push_back(b);
        gr[b].push_back(a);
    }

    Graph graph = Graph(n, gr);

    vector < vector < int > > ans = graph.comp_biconexe();

    fout<<ans.size()<<'\n';
    for (auto &x : ans){
        for (auto &y: x){
            fout<<y<<" ";
        }
        fout<<'\n';
    }

}


int main() {

    solve();

    return 0;
}