Cod sursa(job #3228548)

Utilizator VolterNikolay Volter Data 8 mai 2024 18:49:25
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <set>
#include<fstream>

using namespace std;
ifstream in ( "biconex.in" ) ;
ofstream out ( "biconex.out" ) ;

vector<vector<int>> gr;
vector<int> tim, fun;
vector<bool> used;

stack<int> C;
stack<pair<int,int>> st;

vector<set<int>> point;
int times = 0;
void vert(int u,int v){
    set<int> key;
    int bu,bv;
    do{
        bu=st.top().first;
        bv=st.top().second;
        st.pop();
        key.insert(bu);
        key.insert(bv);
    }while(bu != u || bv !=v );
    point.push_back(key);
}

void dfs(int v,int p=-1){
    used[v]=1;
    tim[v]=times++;
    fun[v]=tim[v];
    int child=0;
    
    for (auto u:gr[v])
    {
        if(u==p){
        continue;
        }

        if(fun[u]== -1){
        st.push({v,u});
        dfs(u,v);
        fun[v]=min(fun[u],fun[v]);
        if(fun[u]>=tim[v])
            vert(v,u);
        }

        else{
           fun[v]=min(fun[v],tim[u]);

        }
 
    }

}

int main() {
    int n, m;
    in >> n >> m;

    gr=vector<vector<int>>(n);
    tim=vector<int>(n);
    fun=vector<int>(n,-1);
    used= vector<bool>(n,0);

    for (int i = 0; i < m; ++i) {
        int u, v;
        in >> u >> v;
        --u; --v; 
        gr[u].push_back(v);
        gr[v].push_back(u);
    }
    in.close();
   
    dfs(0);
    
    out<<point.size()<<"\n";

    for (auto i:point)
    {
        for (auto j:i)
        {
            out<<j+1<<" ";
        }
        out<<"\n";
    }
    out.close();

    return 0;
}