Cod sursa(job #2372489)

Utilizator WayronUrsu Ianis-Vlad Wayron Data 7 martie 2019 09:31:44
Problema Componente biconexe Scor 42
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bits/stdc++.h>
using namespace std;


int n, m;
int indexx = 0;
vector<vector<int>> graph;

vector<int> low;
vector<int> level;

stack<int> Stack;
vector<bool> vizitat;

vector<vector<int>> components;


void biconex(int node){
    level.at(node) = low.at(node) = ++indexx;
    Stack.push(node);
    vizitat.at(node) = true;

    for(auto& kid:graph.at(node)){
        if(vizitat.at(kid)){
            low.at(node) = min(low.at(node), level.at(kid));
            continue;
        }

        biconex(kid);

        low.at(node) = min(low.at(kid), low.at(node));

        if(low.at(kid)>=level.at(node)){
            Stack.push(node);
            vector<int> component;
            int x = Stack.top();
            do {

                Stack.pop();
                component.push_back(x);
                x = Stack.top();

            } while(x!=node);
            components.push_back(component);
        }

    }


}
int main()
{
    ifstream fin("biconex.in");
    ofstream fout("biconex.out");
    fin>>n>>m;
    graph.resize(n+1, vector<int>());

    int x, y;
    for(int i=1; i<=m; i++){
        fin>>x>>y;
        graph.at(x).push_back(y);
        graph.at(y).push_back(x);
    }

    low.resize(n+1);
    level.resize(n+1);
    vizitat.resize(n+1, false);

    biconex(1);

    fout<<components.size()<<endl;

    for(auto& component:components){

        for(auto& element:component) fout<<element<<" ";
        fout<<endl;
    }


}