Cod sursa(job #2610014)

Utilizator RaduNichitaRadu Nichita RaduNichita Data 4 mai 2020 00:31:26
Problema Componente biconexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.12 kb
#include <iostream>
	
#include <vector>
#include <stack>	
#include <fstream>
#include <algorithm>
using namespace std;
	
 
	
 
	
 
	
#define NMAX 100002
	
 
	
class Task {
	
    std::vector<int> matrix[NMAX];
    std::vector<int> index;
    std::vector<int> low;
    std::vector<int> parent;
    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);
        parent = std::vector<int> (N + 1, -1);
        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);
                parent[i] = 0;
            }
        }
    }

    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) {
                parent[neight] = node;
                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 {
                if (neight != parent[node]) {
                    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;
	
}