Cod sursa(job #2672092)

Utilizator AvramDanielAvram Daniel AvramDaniel Data 13 noiembrie 2020 00:39:01
Problema Componente biconexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second

vector<int> v[100010];
vector<set <int> > ans;
int n,m,a,b,t = 1;

bool viz[100010];
int last_min[100010], disc[100010], parent[100010];
stack<pair<int,  int> > st;

void dfs(int x){
   // cout<<x<<' ';
    viz[x] = 1;
    last_min[x] = t;
    disc[x] = t;
    for(auto node: v[x]){
        if(viz[node] && node != parent[x]){
            last_min[x] = min(last_min[x], disc[node]);

        }
        else if(!viz[node]) {
            parent[node] = x;
            st.push({x, node});
            t++;
            dfs(node);
            if(last_min[node] >= disc[x]){
                set<int> s;
                while(st.top() != make_pair(x, node)){
                    s.insert(st.top().fi);
                    st.pop();
                }
                s.insert(st.top().fi);
                s.insert(st.top().se);
                st.pop();
                ans.push_back(s);
            }
            last_min[x] = min(last_min[x], last_min[node]);

        }
    }
}

int main(){

    ifstream cin("biconex.in");
    ofstream cout("biconex.out");

    cin >>n>>m;
    for (int i = 0; i < m; i++){
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    for(int i = 1;i<=n;i++){
        if(!viz[i])
            dfs(i);
    }

    cout<<ans.size()<<'\n';
    for(auto curr: ans)
    {
        for(auto curr2: curr)
            cout<<curr2<<' ';
        cout<<'\n';
    }

    return 0;
}