Cod sursa(job #2562935)

Utilizator EdgeLordXDOvidiuPita EdgeLordXD Data 29 februarie 2020 20:19:41
Problema Componente biconexe Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <bits/stdc++.h>
#define N 100005
#define ll long long
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector<pair<int, int>>a[N];
vector<int>g[N], sol[N];
stack<pair<int,int>>st;
pair<int, int>muches[2*N];
int v[N],v2[N],k=-1, vm[2*N];
void dfs(int i, int j=0, int mucia=0){
    v[i]=i;
    st.push({i,mucia});
    for(auto it:a[i]){
        if(!v[it.first]){
            dfs(it.first,i,it.second);
        }
        else if(v[it.first] && it.first!=j){
            vm[it.second]=1;
            while(!st.empty() && st.top().first!=v[it.first]){
                g[v[it.first]].push_back(st.top().first);
                g[st.top().first].push_back(v[it.first]);
                v[st.top().first]=v[it.first];
                vm[st.top().second]=1;
                st.pop();
            }
        }
    }
    if(!st.empty() && st.top().first==i){
        st.pop();
    }
}
void dfs2(int i){
    sol[k].push_back(i);
    v2[i]=1;
    for(auto it:g[i]){
        if(!v2[it]){
            dfs2(it);
        }
    }
}
int main(){
    int n, m,x,y;
    in>>n>>m;
    for(int i=1; i<=m; ++i){
        in>>x>>y;
        muches[i]={x,y};
        a[x].push_back({y,i});
        a[y].push_back({x,i});
    }
    dfs(1);
    for(int i=1; i<=n; ++i){
        if(!v2[i]){
            ++k;
            dfs2(i);
            if(sol[k].size()==1){
                --k;
            }
        }
    }
    for(int i=1; i<=m; ++i){
        if(!vm[i]){
            sol[++k].clear();
            sol[k].push_back(muches[i].first);
            sol[k].push_back(muches[i].second);
        }
    }
    out<<k+1<<"\n";
    for(int i=0; i<=k; ++i){
        for(auto it:sol[i]){
            out<<it<<" ";
        }
        out<<"\n";
    }
    return 0;
}