Interview

# Description:

https://www.careercup.com/question?id=5721734273564672

## Example:

``````Note
``````

# Code:

``````#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <utility>
#include <memory>
#include <cmath>

using namespace std;

int DFS(unordered_map<int, unordered_set<int>> &relations,  vector<bool> &visited, int i, int n){
visited[i]=true;

if(relations.find(i+1)==relations.end())
return 1;

int number=0;
for(auto e: relations[i+1]){
if(!visited[e-1]){
number += DFS(relations, visited, e-1, n);
}
}
return number+1;
}

int nuclearRodCost(int n, vector<pair<int, int>>& connect){
vector<bool> visited(n, false);
unordered_map<int, unordered_set<int>> relations;

for(auto & e : connect){
relations[e.first].insert(e.second);
relations[e.second].insert(e.first);
}

// for(auto & e: relations){
//     for(auto & e2: e.second){
//         cout<<e.first<<"->"<<e2<<' ';
//     }
//     cout<<'\n';
// }

vector<int> rod_length;

for(int i=0; i<n; ++i){
if(!visited[i]){
rod_length.push_back(DFS(relations, visited, i, n));
// cout<<i<<' '<<rod_length.back()<<endl;
}
}

int sum_cost=0;

for(auto e: rod_length){
// cout<<e<<' ';
// ceiling of sqrt(len), cost for each rod with length len
sum_cost += ceil(sqrt(e));
}
// cout<<endl;

return sum_cost;
}

int main(){

// vector<pair<int, int>> connect={{1, 2}, {1, 4}, {3, 4}};
// int n=6;
vector<pair<int, int>> connect={{1, 2}, {1, 4}};
int n=4;

int result;

result = nuclearRodCost(n, connect);

cout<<result<<endl;
}
``````