Cod sursa(job #2799796)

Utilizator lucriLuchian Cristian lucri Data 13 noiembrie 2021 13:49:13
Problema Componente biconexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
int n,m,x,y,nr;
vector<vector<int>>a,r;
queue<int>s;
bool v[100010],v2[100010];
struct noduri{int l,t;}nod[100010];
void arbore(int i)
{
    bool p=false;
    for(auto x:a[i])
    {
        if(v[x]==false)
        {
            p=true;
            v[x]=true;
            nod[x].l=nod[i].l+1;
            nod[x].t=i;
            arbore(x);
        }
    }
    if(p==false)
        s.push(i);
    return;
}
int main()
{
    in>>n>>m;
    a.resize(n+5);
    r.resize(n+5);
    for(int i=1;i<=m;++i)
    {
        in>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    nod[1].t=0;
    nod[1].l=0;
    for(int i=1;i<=n;++i)
    {
        if(v[i]==false)
        {
            v[i]=true;
            arbore(i);
        }
    }
    while(!s.empty())
    {
        int y=s.front(),nmin;
        s.pop();
        if(v2[y]==true||y==1)
            continue;
        nmin=nod[y].l;
        ++nr;
        v2[y]=true;
        for(auto x:a[y])
        {
            if(nmin>nod[x].l&&nod[x].l+1!=nod[y].l)
                nmin=nod[x].l;
        }
        r[nr].push_back(y);
        y=nod[y].t;
        while(nmin<nod[y].l)
        {
            v2[y]=true;
            r[nr].push_back(y);
            for(auto x:a[y])
            {
                if(nmin>nod[x].l&&nod[x].l+1!=nod[y].l)
                    nmin=nod[x].l;
            }
            y=nod[y].t;
        }
        r[nr].push_back(y);
        s.push(y);
    }
    out<<nr<<'\n';
    for(int i=1;i<=nr;++i)
    {
        for(auto x:r[i])
            out<<x<<' ';
        out<<'\n';
    }
    return 0;
}