Cod sursa(job #3223790)

Utilizator Alex_DumitrascuAlex Dumitrascu Alex_Dumitrascu Data 13 aprilie 2024 16:43:44
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
vector <int> g[100005];
int level[100005];
int low[100005];
int used[100005];
bool articulatie[100005];
bool used_biconex[100005];
vector <int> sol[100005];
int ind=0;
stack <int> st;
void dfs(int nod, int tata)
{
    int nrsons=0;
    used[nod]=1;
    level[nod]=level[tata]+1;
    low[nod]=level[nod];
    st.push(nod);
    for (int vecin : g[nod]) {
        if (vecin==tata) continue;
        if (!used[vecin]) {
            nrsons++;
            dfs(vecin, nod);
            low[nod]=min(low[nod], low[vecin]);

            if (low[vecin]>=level[nod]) {
                articulatie[nod]=1;
                if (low[vecin]>=level[nod]) {
                    while (!st.empty()&&st.top()!=vecin) {
                        sol[ind].push_back(st.top());
                        st.pop();
                    }
                    sol[ind].push_back(st.top());
                    st.pop();
                    sol[ind].push_back(nod);
                    ind++;
                }
            }

        }
        else {
            low[nod]=min(low[nod], level[vecin]);
        }
    }
    if (tata==0&&nrsons==1) articulatie[nod]=0;
    used[nod]=2;
}
int main()
{
    fin.tie(0); fin.sync_with_stdio(false);
    int n, m, a, b; fin>>n>>m;
    for (int i=1; i<=m; i++) {
        fin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i=1; i<=n; i++) {
        low[i]=INT_MAX;
        level[i]=INT_MAX;
    }
    level[0]=-1;
    dfs(1, 0);
    //for (int i=1; i<=n; i++) if (articulatie[i]) cout<<i<<' ';
    fout<<ind<<'\n';
    for (int i=0; i<ind; i++) {
        for (int nod : sol[i]) {
            fout<<nod<<' ';
        }
        fout<<'\n';
    }
    return 0;
}