Cod sursa(job #2758787)

Utilizator lahayonTester lahayon Data 12 iunie 2021 21:28:25
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.22 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>


using namespace std;

void dfs(int node, int& index, vector<int>& disc, vector<int>& lowlink, stack<pair<int, int>>& Edges, const vector<vector<int>>& graph, vector<vector<int>>& components){

    disc[node] = lowlink[node] = ++index;
    for(auto adjacent : graph[node]){
        if(disc[adjacent] == -1){
            Edges.push(pair<int, int>(node, adjacent));
            dfs(adjacent, index, disc, lowlink, Edges, graph, components);
            lowlink[node] = min(lowlink[node], lowlink[adjacent]);

            if(lowlink[adjacent] >= disc[node]){
                vector<int> component;
                int x, y;
                do{
                    x = Edges.top().first; y = Edges.top().second;
                    Edges.pop();
                    component.push_back(x);
                    component.push_back(y);
                }while(!Edges.empty() && x != node && y != adjacent);
                sort(component.begin(), component.end());
                component.erase(unique(component.begin(), component.end()), component.end());
                components.push_back(component);

            }
        }
        else lowlink[node] = min(lowlink[node], disc[adjacent]);
    }
}


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

    int N, M;
    cin >> N >> M;

   vector<vector<int>> graph;
   vector<int> disc, lowlink;

   for(int i = 0; i < N; ++i){
       graph.push_back({});
       disc.push_back(-1);
       lowlink.push_back(-1);
   }

   for(int x, y; M > 0; --M){
       cin >> x >> y;
       --x; --y;
       graph[x].push_back(y);
       graph[y].push_back(x);
   }

    vector<vector<int>> components;

    int index = 0;

    for(int i = 0; i < N; ++i)
        if(disc[i] == -1){
             stack<pair<int, int>> Edges;
             dfs(i, index, disc, lowlink, Edges, graph, components);
        }   
   
    cout << components.size() << "\n";
    for(auto component : components){
        for(auto cmp : component)
            cout << cmp + 1 << " ";
        cout << "\n";
    }

    cin.close();
    cout.close();

    return 0;
}