Cod sursa(job #2660541)

Utilizator stanciucalinStanciu Calin stanciucalin Data 19 octombrie 2020 18:08:10
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.8 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <set>
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];

stack <pair <int, int>> graph_search;
vector <vector <pair <int, 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];

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

        int next_node = lv[node][i];
        pair <int, int> edge(node, next_node);

        if (!visited[next_node]){

            n_children += 1;

            graph_search.push(edge);
            ///cout << "added " << edge.first << " " << edge.second << " | ";
            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 && n_children > 1)){  ///cazul cand descopar un nod de articulatie

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

                while (graph_search.top() != edge){
                    ///cout << "popped " << graph_search.top().first << " " << graph_search.top().second << " | ";
                    biconnected_components[biconnected_components.size() - 1].push_back(graph_search.top());
                    graph_search.pop();
                }
                ///cout << "popped " << graph_search.top().first << " " << graph_search.top().second << " | ";
                biconnected_components[biconnected_components.size() - 1].push_back(graph_search.top());
                graph_search.pop();
            }

        }
        else if(next_node != parent && low_level[node] > level[next_node]){ /// tratez cazul cand exista o muchie de intoarcere

            low_level[node] = level[next_node];
            ///cout << "added " << edge.first << " " << edge.second << " | ";
            graph_search.push(edge); /// adaug si muchiile de intoarcere
        }
    }
}

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]){

            DFS(i, -1);

            if(!graph_search.empty()){

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

                while(!graph_search.empty()){

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

    g << biconnected_components.size() << '\n';

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

        set <int> shown;

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

            int n1 = biconnected_components[i][j].first;
            int n2 = biconnected_components[i][j].second;

            if(shown.find(n1) == shown.end() ){

                g << n1 << " ";
                shown.insert(n1);
            }
            if(shown.find(n2) == shown.end() ){

                g << n2 << " ";
                shown.insert(n2);
            }
            ///g << biconnected_components[i][j].first << " " << biconnected_components[i][j].second << " | ";
        }
        g << '\n';
    }

    return 0;
}