Cod sursa(job #2634618)

Utilizator HannaLieb Hanna Hanna Data 11 iulie 2020 18:06:30
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 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<pair<int,int> >v;

int n,m,i,a,b;

vector<set<int> >komp;

void ujkomp(pair<int,int> p)
{
    set<int>s;
    pair<int,int> k;

    do
    {
        k=v.top();
        v.pop();
        s.insert(k.first);
        s.insert(k.second);
    }
    while(k!=p);

    komp.push_back(s);
}

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

    for(auto e : x[i].s)
    if(e!=apa)
    {
        if(!x[e].l)
        {
            v.push({i,e});
            melysegi(e,lep+1,i);
            x[i].mp=min(x[i].mp,x[e].mp);
            if(x[e].mp>=x[i].lep) ujkomp({i,e});
        }
        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;
}