Cod sursa(job #2798041)

Utilizator Marie02THGStanescu Maria Raluca Marie02THG Data 10 noiembrie 2021 20:42:43
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.12 kb
#include<bits/stdc++.h>

using namespace std;

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

vector<int> la[100005]; ///lista de adiacenta
vector <set <int>> componente;
//stack <int>s;

stack<pair<int, int>> stivaCB;
int minim[100005];    ///nivelul minim in care putem ajunge din nodul urent in subtree ul curent
bool vizitat[100005]; ///vectorul de vizitat ( 0 -neviz , 1- viz)
int discovery[100005]; ///primul moment in care trecem prin nod in dfs
static int moment = 1; ///contorizam momentul de trecere prin noduri


void dfsbiconex(int nod_curent, int nod_precedent)
{
    discovery[nod_curent] = moment;
    minim[nod_curent] = moment;
    vizitat[nod_curent] = true;
    moment++;

    for(int i=0 ; i < la[nod_curent].size() ; i++)
    {
        int nod_adiacent = la[nod_curent][i];

        // if (nod_adiacent != nod_precedent)
        // {

        if (vizitat[nod_adiacent] == false)
        {
            stivaCB.push(make_pair(nod_curent, nod_adiacent)); ///punem muchia curenta in stiva

            dfsbiconex(nod_adiacent, nod_curent);  ///continuam dfs

            if (minim[nod_curent] > minim[nod_adiacent]) /// daca nodul adiacent face parte din acelasi subtree cu nodul curent
                minim[nod_curent] = minim[nod_adiacent]; ///at. momentul minim la care putem ajunge din el e acelasi cu momentul minim in care ajungem din nodul curent

            if (minim[nod_adiacent] >= discovery[nod_curent]) ///comp. biconexa (pt. ca mom. min coresp. nodului adiacent este mai mare sau = cu prima data cand trecem prin nodul curent in dfs
            {
                set<int> noduri_cb; ///setul cu nodurile din componenta biconexa
                int nod1, nod2;
                do
                {
                    nod1 = stivaCB.top().first;
                    nod2 = stivaCB.top().second;
                    noduri_cb.insert(nod1);
                    noduri_cb.insert(nod2);
                    stivaCB.pop();
                }
                while (nod1 != nod_curent || nod2 != nod_adiacent); ///nu am gasit un element care se repeta

                componente.push_back(noduri_cb);
            }

        }
        else  ///nodul curent a fost vizitat
        {
            if (minim[nod_curent] > discovery[nod_adiacent])  ///avem muchie de intoarcere de la nodul adiacent la nodul curent(am trecut deja prin nodul adiacent)
            {

                minim[nod_curent] = discovery[nod_adiacent]; ///minimul se actualizeaza cu momentul in care am dat de nodul adiacent deja vizitat
            }
        }
        // }
    }
}

int main()
{
    int n,m;
    in>>n>>m; ///citim nr noduri + nr muchii
    for(int i=1; i<=m; i++)
    {
        int a,b;
        in>>a>>b;
        ///graf neorientat
        la[a].push_back(b);
        la[b].push_back(a);
    }

    dfsbiconex(1, 0);
    out<< componente.size() <<'\n';

    set<int>::iterator it;
    for (auto &i: componente)
    {
        for (it = i.begin(); it != i.end(); it++)
        {

            out << *it << " ";
        }
        out << "\n";
    }

    return 0;

}