Cod sursa(job #2832573)

Utilizator enestianEne Sebastian enestian Data 13 ianuarie 2022 22:15:22
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.16 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

int N;
int M;
int start;
vector<vector<int>> vecini;

void citire_graf() {
        f >> N;
        f >> M;
        int nod1, nod2;
        vecini.resize(N + 1);
        for (int i = 0; i < M; i++) {
            f >> nod1 >> nod2;
            vecini[nod1].push_back(nod2);
            vecini[nod2].push_back(nod1);
        }
}



void DFS_biconex(vector<bool>& vizitat, int fiu, int tata, vector<int>& nivel, vector<int>& low, stack<int>& stack, vector<vector<int>>& compConexe, int& nrCC) {
    vizitat[fiu] = true;
    stack.push(fiu);
    nivel[fiu] = nivel[tata] + 1;
    low[fiu] = nivel[fiu];
    int i;
    for (i = 0; i < vecini[fiu].size(); i++)
        if (vecini[fiu][i] != tata) {//mergem depth, nu in sus, evitam sa mergem in sus
            if (vizitat[vecini[fiu][i]] == true) {//daca am mai vizitat nodul, ii vedem val de low, 
                                                  //daca e mai mare ca a nodului cu care e legat, luam valoarea aceea mai mica
                if (low[fiu] > nivel[vecini[fiu][i]]) 
                        low[fiu] = nivel[vecini[fiu][i]];
            }
            else {
                DFS_biconex(vizitat, vecini[fiu][i], fiu, nivel, low, stack, compConexe, nrCC);//altfel, nevizitat si mergem in continuare cu un DFS, iar tata devine fiu, fiu devine next vecin al fiului initial
                if (low[fiu] > low[vecini[fiu][i]]) //low de la tatal nod merge in jos la fiu practic in cazul in care fiul are low mai mare
                        low[fiu] = low[vecini[fiu][i]];

                if (nivel[fiu] <= low[vecini[fiu][i]]) {//cand nivel tata ajunge (maxim) egal cu low de vecin,in genere egal, inseamna ca avem back path si putem forma componentele conexe, ca am gasit ciclu si nod de articulatie
                    while (stack.top() != vecini[fiu][i]) {
                        compConexe[nrCC].push_back(stack.top());//scoatem din stiva rand pe rand elementele afara de fiu si tata si le retinem in vectorul de componente conexe
                        stack.pop();
                    }
                    compConexe[nrCC].push_back(vecini[fiu][i]);
                    stack.pop();
                    compConexe[nrCC].push_back(fiu);
                    nrCC++;
                }
            }
        }
}

void biconex_init_si_print() {
    vector<bool> vizitat(N + 1, false);
    vector<int> nivel(N + 1);//vector de nivele 
    nivel[0] = 0;
    vector<int> low(N + 1);//vector de low level pentru fiecare nod
    low[0] = 0;
    stack<int> stack;  //stiva cu nodurile vizitate
    vector<vector<int>> compConexe;
    compConexe.resize(N + 1); 
    int tata = 0;
    int fiu = 1;
    int nrCC = 0;

    DFS_biconex(vizitat, fiu, tata, nivel, low, stack, compConexe, nrCC);
    g << nrCC << '\n';
    for (int i = 0; i < nrCC; i++) {
        for (int j = 0; j < compConexe[i].size(); j++)
            g << compConexe[i][j] << " ";
        g << '\n';
    }
}

int main()
{
    citire_graf();
    biconex_init_si_print();
	return 0;
}