Cod sursa(job #2634615)

Utilizator HannaLieb Hanna Hanna Data 11 iulie 2020 17:52:37
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>

using namespace std;

ifstream cin("biconex.in");
ofstream cout("biconex.out");

struct adat
{
    bool l;
    int lep,mp;
    vector<int>s;
};
vector<adat>x;
stack<int>v;

int n,m,i,a,b;

vector<set<int> >komp;

void ujkomp(int i)
{
    set<int>s;
    int k;

    k=v.top();

    while(k!=i)
    {
        v.pop();
        s.insert(k);
        k=v.top();
    }
    s.insert(i);

    komp.push_back(s);
}

void melysegi(int i, int lep, int apa)
{
    x[i].lep=lep;
    x[i].mp=lep;
    x[i].l=true;
    v.push(i);

    for(auto e : x[i].s)
    if(e!=apa)
    {
        if(!x[e].l)
        {
            melysegi(e,lep+1,i);
            x[i].mp=min(x[i].mp,x[e].mp);
            if(x[e].mp>=x[i].lep) ujkomp(i);
        }
        else x[i].mp=min(x[i].mp,x[e].lep);
    }
}

int main()
{
    cin>>n>>m;
    x.resize(n+1);
    for(i=1;i<=m;++i)
    {
        cin>>a>>b;
        x[a].s.push_back(b);
        x[b].s.push_back(a);
    }

    melysegi(1,1,0);

    cout<<komp.size()<<"\n";
    for(auto e : komp)
    {
        for(auto f : e) cout<<f<<" ";
        cout<<"\n";
    }

    return 0;
}