Cod sursa(job #2663939)

Utilizator ddeliaioanaaDumitrescu Delia Ioana ddeliaioanaa Data 27 octombrie 2020 17:19:56
Problema Componente biconexe Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.02 kb
#include <bits/stdc++.h>

std::ifstream fin("biconex.in");
std::ofstream fout("biconex.out");

int n, m;
std::vector<int> nei[100001], rank, low;
std::stack <std::pair <int, int>> search;
std::vector<std::vector<int>> comp;

void addBiconnectedComp(int x, int node){  //eliminam muchiile din stiva si adaugam componenta biconexa
    std::vector<int> aux;
    int aux1 = search.top().first;
    int aux2 = search.top().second;
    search.pop();
    aux.push_back(aux1);
    aux.push_back(aux2);
    while(aux1 != x && aux2 != node){
        aux1 = search.top().first;
        aux2 = search.top().second;
        search.pop();
        if(find(aux.begin(), aux.end(), aux1) == aux.end())
            aux.push_back(aux1);
        if(find(aux.begin(), aux.end(), aux2) == aux.end())
            aux.push_back(aux2);
    }
    comp.push_back(aux);
}

void dfs(int x, int parent, int step)
{
    rank[x] = step;
    low[x] = step;
    for(auto node: nei[x]){ // parcurgem vecinii
        if(rank[node] == -1){ //nevizitat
                search.push(std::make_pair(x, node));
                dfs(node, x, step + 1);
                low[x] = std::min(low[x], low[node]); //actualizam low-> x poate ajunge mai sus folosind orice muchie de intoarcere a copiilor
                if(low[node] >= rank[x])// x e punct de articulatie => eliminam toate muchiile din stiva si actualizam comp
                    addBiconnectedComp(x, node);
            }
        else{ //nodul e deja vizitat, deci e muchie de intoarcere
            low[x] = std::min(low[x], rank[node]);
        }
    }
}

int main()
{
    int x, y, i;
    fin >> n >> m;
    rank.resize(n + 1, -1); // rank[i] = al catelea nod a fost i in parcurgerea dfs
    low.resize(n + 1); // low[i] =

    for(i = 0; i < m; i++){
        fin >> x >> y;
        nei[x].push_back(y);
        nei[y].push_back(x);
    }

    dfs(1, 0, 0);

    fout << comp.size() << '\n';
    for(auto i: comp){
        sort(i.begin(), i.end());
        for(auto j: i)
            fout << j << " ";
        fout << '\n';
    }

    return 0;
}