Cod sursa(job #2478401)

Utilizator joy333Steluta Talpau joy333 Data 21 octombrie 2019 23:52:29
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.96 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_map>
using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

class Solution{
public:
    int min_reachable(int root, int parent,  vector<vector<int>>&answer, int step,
    unordered_map<int,int>&value_visited_time_pair, unordered_map<int,vector<int>>&minimum_reachable_poz_node_pair,vector<vector<int>>&lista_adiacenta){

        int min_reachable_from_root = step;
        for(unsigned int i=0; i<lista_adiacenta[root].size();i++ ){
            int current_child = lista_adiacenta[root][i];
            auto it = value_visited_time_pair.find(current_child);
            if(current_child == parent){
                continue;
            }
            if(it == value_visited_time_pair.end()){
                step+=1;
                value_visited_time_pair.insert(make_pair(current_child,step));
                min_reachable_from_root =  min(min_reachable_from_root,
                min_reachable(current_child,root,answer,step,value_visited_time_pair,minimum_reachable_poz_node_pair,lista_adiacenta));
            }
            else{
                min_reachable_from_root =  min(min_reachable_from_root,it->second);
            }

        }
        if(parent ==0){
            return 0;
        }
        if(min_reachable_from_root> value_visited_time_pair[parent]){
            vector<int> aux;
            aux.push_back(root);
            aux.push_back(parent);
            answer.push_back(aux);
        }
        auto it2 = minimum_reachable_poz_node_pair.find(min_reachable_from_root);
        if(it2 == minimum_reachable_poz_node_pair.end()){
            vector<int>aux;
            aux.push_back(root);
            minimum_reachable_poz_node_pair.insert(make_pair(min_reachable_from_root,aux));
        }
        else{
            it2->second.push_back(root);
        }
        return min_reachable_from_root;


    }




};

int main()
{
    int nr_noduri, nr_muchii;
    vector<int>aux;
    vector<vector<int>>lista_adiacenta(nr_noduri+1,aux);
    fin>>nr_noduri>>nr_muchii;
    for(int i=0; i< nr_muchii; i++){
        int nod_1,nod_2;
        fin>>nod_1>>nod_2;
        lista_adiacenta[nod_1].push_back(nod_2);
        lista_adiacenta[nod_2].push_back(nod_1);
    }
    vector<vector<int>>answer;
    unordered_map<int,int>value_visited_time_pair;
    value_visited_time_pair.insert(make_pair(1,1));
    unordered_map<int,vector<int>>minimum_reachable_poz_node_pair;
    Solution s;
    s.min_reachable(1,0,answer,1,value_visited_time_pair,minimum_reachable_poz_node_pair,lista_adiacenta);
    for(auto it = minimum_reachable_poz_node_pair.begin(); it!= minimum_reachable_poz_node_pair.end();it++){
        if(it->second.size()>1){
            answer.push_back(it->second);
        }
    }
    fout<<answer.size()<<"\n";
    for(unsigned int i=0; i<answer.size();i++){
        for(unsigned int j= 0; j<answer[i].size();j++){
            fout<<answer[i][j]<<" ";
        }
        fout<<"\n";
    }




    return 0;
}