Cod sursa(job #2513648)

Utilizator EdgeLordXDOvidiuPita EdgeLordXD Data 23 decembrie 2019 16:12:52
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <fstream>
#include <vector>
#include <set>
#include <stack>
#define N 100005
#define ll long long
#define f first
#define s second
using namespace std;
ifstream in("in.txt");
ofstream out("out.txt");
vector<pair<ll,ll>> a[N], mu;
vector<ll> rez[2*N];
set<ll> sol[2*N];
stack<ll> st;
bool v[N], vm[2*N];
ll k=0;
void dfsm(ll i){
    vm[i]=1;
    sol[k].insert(mu[i].f);
    sol[k].insert(mu[i].s);
    for(auto it:rez[i])
        if(!vm[it])
            dfsm(it);
}
void dfs(ll i, ll j){
    v[i]=1;
    for(auto it:a[i])
        if(!v[it.f]){
            st.push(it.s);
            dfs(it.f, it.s);
        }
        else if(v[it.f] && j!=it.s){
            for(auto itt:a[it.f])
                if(vm[itt.s]){
                    rez[it.s].push_back(itt.s);
                    rez[itt.s].push_back(it.s);
                }
            vm[it.s]=1;
            while(!st.empty()){
                rez[it.s].push_back(st.top());
                rez[st.top()].push_back(it.s);
                vm[st.top()]=1;
                if(mu[st.top()].f==it.f || mu[st.top()].s==it.f)
                    break;
                st.pop();
            }
        }
    while(!st.empty() && st.top()!=j)
        st.pop();
}
int main() { 
    ll n, m,i,x,y;
    in>>n>>m;
    for(i=0; i<m; ++i){
        in>>x>>y;
        a[x].push_back({y,i});
        a[y].push_back({x,i});
        mu.push_back({x,y});
    }
    dfs(1,-1);
    for(i=0; i<m; ++i)
        vm[i]=0;
    for(i=0; i<m; ++i)
        if(!vm[i]){
            dfsm(i);
            ++k;
        }
    out<<k<<"\n";
    for(i=0; i<k; ++i){
        for(auto it:sol[i])
            out<<it<<" ";
        out<<"\n";
    }
    return 0;
}