Cod sursa(job #2610038)

Utilizator RaduNichitaRadu Nichita RaduNichita Data 4 mai 2020 01:18:01
Problema Componente biconexe Scor 100
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 3.28 kb
#include <iostream>
	
	
	
#include <vector>
	
#include <stack>	
	
#include <fstream>
	
#include <algorithm>
	
using namespace std;
	
	
	
 
	
	
	
 
	
	
	
 
	
 
	
	
	
 
	
	
	
class Task {
	
	
	
    std::vector<std::vector<int>> matrix;
	
    std::vector<int> index;
	
    std::vector<int> low;
	
    std::stack<std::pair <int, int>> sc;
	
    std::vector<std::vector<int>> biconex;
	
    int ctime;
	
    int N;
	
    int M;
	
	
	
 
	
	
	
    void read_input() {
	
	
	
        std::ifstream in("biconex.in");
	
 
	
        in >> N;
	
        index = std::vector<int> (N + 1, -1);
	
        low = std::vector<int> (N + 1);
	
        matrix = std::vector<std::vector<int>> (N + 1, std::vector<int>());
	
        ctime = 0;
	
 
	
        in >> M;
	
        for (int i = 0; i < M; i++) {
	
	
	
            int x, y;
	
            in >> x >> y;
	
            matrix[x].push_back(y);
	
            matrix[y].push_back(x);
	
        }
	
        in.close();
	
	
	
    }
	
	
	
 
	
	
	
    void show_matrix() {
	
	
	
        for (int i = 0; i < N; i++) {
	
	
	
            std::cout<<i<<":";
	
	
	
            for (int j = 0; j < matrix[i].size(); j++) {
	
                std::cout<<matrix[i][j]<<" ";
	
            }
	
            std::cout<<"\n";
	
	
	
        }
	
	
	
    }
	
	
	
 
	
	
	
    
	
	void get_biconnex_components() {
	
        for (int i = 1; i <= N; i++) {
	
            if (index[i] == -1) {
	
                biconex_component_tarjan(i);
	
            }
	
        }
	
    }
	
 
	
    void biconex_component_tarjan(int node) {
	
        index[node] = ctime;
	
        low[node] = ctime;
	
        ctime++;
	
        int children = 0;
	
 
	
        for (auto const &neight : matrix[node]) {
	
            if (index[neight] == -1) {
	
                children++;
	
                sc.push ({node, neight});
	
                biconex_component_tarjan(neight);
	
                low[node] = std::min (low[node], low[neight]);
	
                if (low[neight] >= index[node]) {
	
                    get_biconnex({node, neight});
	
                }
	
            } else {
	
                low[node] = std::min(low[node], index[neight]);
	
            }
	
        }
	
 
	
    }
	
 
	
 
	
    void  get_biconnex(std::pair<int, int> target_edge) {
	
        std::vector<int> bcc;
	
        std::pair<int, int> edge = {-1, -1};
	
        while (edge != target_edge) {
	
            edge = sc.top();
	
            bcc.push_back(edge.first);
	
            bcc.push_back(edge.second);
	
            sc.pop();
	
        }
	
        std::sort(bcc.begin(), bcc.end());
	
        auto it = std::unique(bcc.begin(), bcc.end());
	
        bcc.erase(it, bcc.end());
	
        biconex.push_back(bcc);
	
    }
	
	
	
    void print() {
	
	
	
        std::ofstream out("biconex.out");   
	
        out<<biconex.size()<<"\n";
	
	
	
        for (auto const &vector : biconex) {
	
            for (auto const &elem : vector) {
	
                out<<elem <<" ";
	
            } 
	
            out<<"\n";
	
        }
	
 
	
        out.close();
	
	
	
        return;
	
	
	
    }
	
	
	
 
	
	
	
 public:
	
	
	
    void solve() {
	
	
	
        read_input();
	
        get_biconnex_components();
	
        print();
	
	
	
    }
	
	
	
 
	
	
	
};
	
	
	
 
	
	
	
int main() {
	
	
	
 
	
	
	
    Task* task = new Task();
	
    task->solve();	
	
    delete(task);
	
    return 0;
	
	
	
}