Cod sursa(job #2660341)

Utilizator stanciucalinStanciu Calin stanciucalin Data 18 octombrie 2020 22:38:56
Problema Componente biconexe Scor 34
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.48 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <stack>
using namespace std;

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

int n, m;
vector <int> lv[100005];

int visited[100005];

int level[100005];
int low_level[100005];
set <int> articulation_points;

stack <int> graph_search;
vector <vector <int>> biconnected_components;

void DFS(int node, int parent){

    int n_children = 0;

    level[node] = level[parent] + 1;
    visited[node] = 1;
    low_level[node] = level[node];

    graph_search.push(node);

    for (int i = 0; i < lv[node].size(); i++){

        int next_node = lv[node][i];

        if (!visited[next_node]){

            n_children += 1;

            DFS(next_node, node);

            low_level[node] = min(low_level[node], low_level[next_node]); /// tratez cazul cand unul din nodurile din subarborele fiului are o muchie de intoarcere

            if ((low_level[next_node] >= level[node] && parent != -1) || (parent == -1 && lv[node].size() > 1)){

                biconnected_components.resize(biconnected_components.size() + 1);

                while (graph_search.top() != node){

                    biconnected_components[biconnected_components.size() - 1].push_back(graph_search.top());
                    graph_search.pop();
                }

                biconnected_components[biconnected_components.size() - 1].push_back(graph_search.top());
            }

        }
        else if(next_node != parent){ /// tratez cazul cand exista o muchie de intoarcere

            low_level[node] = min(level[next_node], low_level[node]);
        }
    }
}

int main(){

    f >> n >> m;

    int x, y;
    for(int i = 0; i < m; i++){

        f >> x >> y;
        lv[x].push_back(y);
        lv[y].push_back(x);
    }

    /*for(int i = 1; i <= n; i++){
        cout << i << ": ";
        for (int j = 0; j < lv[i].size(); j++)
            cout << lv[i][j] << " ";
        cout << '\n';
    }*/

    for(int i = 1; i <= n; i++){

        if (!visited[i]){

            while (!graph_search.empty())
                graph_search.pop();

            DFS(i, -1);
        }
    }
    g << biconnected_components.size() << '\n';

    for(int i = 0; i < biconnected_components.size(); i++){

        for(int j = 0; j < biconnected_components[i].size(); j++){

            g << biconnected_components[i][j] << " ";
        }
        g << '\n';
    }

    return 0;
}