Nuclear Rods

Interview

Description:

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

Example:

Note

Idea:

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;
}