Cod sursa(job #3225752)

Utilizator tudor_costinCostin Tudor tudor_costin Data 18 aprilie 2024 18:44:37
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int Nmax=1e5+5;
vector<int> v[Nmax];
int dfn[Nmax],low[Nmax];
vector<vector<int>> ans;
bitset<Nmax> viz;
stack<pair<int,int>> st;
///DFN = timpul la care am intrat intr-un nod prima oara
///LOW = timpul minim(DFN-ul minim) la care ajung in arborele dfs din nod
///punct de articulatie , daca dfn[nod]<=low[copil]
///deoarece oricum merg,ajung din copil intr-un nod cu
///timp mai mare ca nod, formand astfel o componenta biconexa
void createans(int x,int y)
{
    vector<int> comp;
    int tx=-1,ty=-1;
    while(tx!=x || ty!=y)
    {
        tx=st.top().first;
        ty=st.top().second;
        st.pop();
        comp.push_back(ty);
        if(tx==x && ty==y) comp.push_back(tx);
    }
    ans.push_back(comp);
}
void dfs(int nod,int prev,int timp)
{
    viz[nod]=1;
    dfn[nod]=timp;
    low[nod]=timp;
    for(int u:v[nod])
    {
        ///if(nod==1) cout<<u<<' ';
        if(u==prev) continue;
        if(!viz[u])
        {
            st.push({nod,u});
            dfs(u,nod,timp+1);
            low[nod]=min(low[nod],low[u]);
            ///cout<<nod<<' '<<u<<' '<<dfn[nod]<<' '<<low[u]<<'\n';
            if(dfn[nod]==low[u] || dfn[nod]==low[u]-1)
            {
                createans(nod,u);
            }
        }
        else
        {
            low[nod]=min(low[nod],dfn[u]);
        }
    }
    return;
}
int main()
{
    int n,m;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0,0);
    fout<<ans.size()<<'\n';
    for(auto v:ans)
    {
        for(auto x:v)
        {
            fout<<x<<' ';
        }
        fout<<'\n';
    }
    return 0;
}