Cod sursa(job #3312754)

Utilizator vlad7654vladimir manescu vlad7654 Data 29 septembrie 2025 20:06:38
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<vector<int> > graph;
struct componenta_biconexa{
    vector<int> tin, low;
    vector<vector<int> > componente;
    stack<pair<int,int> > s;
    componenta_biconexa(vector<vector<int> >& graph, int n)
    :tin(n+1, -1), low(n+1)
    {
        dfs(graph, 1, 0, 0);
    }
    void punct_de_articulatie(int x, int y){
        int tx, ty;
        vector<int> v;
        while(tx!=x or ty!=y){
            tx=s.top().first;
            ty=s.top().second;
            s.pop();
            v.push_back(tx);
            v.push_back(ty);
        }
        componente.push_back(v);
    }
    void dfs(vector<vector<int> >& graph, int nod, int parent, int k){
        tin[nod]=low[nod]=k;
        for(auto it:graph[nod]){
            if(it!=parent and tin[it]==-1){
                s.push({nod,it});
                dfs(graph, it, nod, k+1);
                low[nod]=min(low[nod], low[it]);
                if(low[it]>=tin[nod]){
                    punct_de_articulatie(nod, it);
                }
            }else if(tin[it]!=-1){
                low[nod]=min(low[nod], tin[it]);
            }
        }
    }
    void query(){
        cout<<component.size()<<'\n';
        for(auto it:componente){
            sort(it.begin(),it.end());
            it.erase(unique(it.begin(),it.end()), it.end());
            for(auto i:it){
                fout<<i<<' ';
            }
            fout<<'\n';
        }
    }
};
int main(){
    int n, m;
    fin>>n>>m;
    graph.resize(n+1);
    for(int i=1;i<=m;i++){
        int x, y;
        fin>>x>>y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    componenta_biconexa ans(graph, n);
    ans.query();
}