Pagini recente » Cod sursa (job #2897686) | Cod sursa (job #2705352) | Cod sursa (job #530972) | Cod sursa (job #805851) | Cod sursa (job #2478401)
#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;
}