Nu aveti permisiuni pentru a descarca fisierul grader_test6.ok

Cod sursa(job #2634625)

Utilizator HannaLieb Hanna Hanna Data 11 iulie 2020 18:32:36
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.48 kb
/**
Ketszeresen osszefuggo komponensek

Egy komponens ketszeresen osszefugo, ha 1 tetszoleges pontot kiveve belole, a komponens maradeka osszefuggo marad.

Melysegivel csinaljuk. Minden pontra eltaroljuk a melyseget, es a hozza tartozo legnagyobb melyseget: melypont.
Ez a melypont kezdetben = a csomopont melysegevel, de ha talalok egy leszarmazottat, akit meg nem lattam es a melypontja
kisebb nala, akkor kicserelem, ha pedig egy olyan leszarmazottat talalok, akit mar lattam, es a melysege < a melypontomnal,
akkor is kicserelem. Kozben mindig beteszem egy verembe az eleket, amiken jartam. Ha egy pontbol visszaerve latom, hogy
annak a pontnak a melypontja, ahova mentem >= mint az aktualisnak a melysege (vagyis vagy alattam, vagy bennem er veget a kor),
akkor az adott pont egy elvagopont lesz, es kapok egy uj ketszeresen osszefuggo komponenst. Ezt ugy kapom meg, hogy kiveszem
a verembol a felso eleket, addig amig meg nem talalom az aktualis elt, amit nezek. Ezeket a pontokat beteszem egy set-be
es o lesz egy uj komponensem.
**/
#include <fstream>
#include <vector>
#include <stack>
#include <set>

using namespace std;

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

struct adat
{
    bool l; ///lattam-e mar
    int lep,mp; ///lep-melyseg, mp-melypont
    vector<int>s;   ///szomszedok
};
vector<adat>x;
stack<pair<int,int> >v;

int n,m,i,a,b;

vector<set<int> >komp;  ///ez a megoldasom

void ujkomp(pair<int,int> p)    ///legyartom az uj komponenst
{
    set<int>s;
    pair<int,int> k;

    do
    {
        k=v.top();
        v.pop();
        s.insert(k.first);
        s.insert(k.second);
    }
    while(k!=p);    ///veszem ki felulrol az eleket, amig meg nem talalom az aktualisat

    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;
}