Cod sursa(job #2732734)

Utilizator robert.barbu27robert barbu robert.barbu27 Data 29 martie 2021 11:10:51
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("biconex.in");
ofstream fout ("biconex.out");

struct nodS
{
    bool viz;
    int id, low;
    vector<int> v;
};

int n,m,x,y,i,nr;
nodS nod[100005];
vector< vector<int> > ans;
vector<pair<int, int>> st;

void add(int x, int y)
{
    vector<int> nv;
    while(true)
    {
        int a=st.back().first;
        int b=st.back().second;
        st.pop_back();

        nv.push_back(a);
        nv.push_back(b);

        if(a==x && b==y)
            break;
    }

    ans.push_back(nv);
}
void dfs(int p, int par)
{
    nr++;
    nod[p].id=nr;
    nod[p].low=nr;
    nod[p].viz=true;

    for(int it : nod[p].v)
    {
        if(it==par)
            continue;

        if(!nod[it].viz)
        {
            st.push_back({p, it});
            dfs(it, p);
            nod[p].low=min(nod[p].low, nod[it].low);

            if(nod[it].low >= nod[p].id)
                add(p, it);
        }
        else
            nod[p].low=min(nod[p].low, nod[it].id);
    }
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        nod[x].v.push_back(y);
        nod[y].v.push_back(x);
    }

    dfs(1, 0);

    fout<<ans.size()<<'\n';
    for(auto &it : ans)
    {
        sort(it.begin(), it.end());
        it.erase(unique(it.begin(), it.end()), it.end());

        for(int it2 : it)
            fout<<it2<<' ';
        fout<<'\n';
    }
    return 0;
}