We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Kruskal (MST): Really Special Subtree
  5. Discussions

Kruskal (MST): Really Special Subtree

Sort by

recency

|

190 Discussions

|

  • nichole_king
     + 0 comments

    As a hint to anyone stuck on a difficult test, I would recommend a couple of things: 1. consider what properties of the graph would make you would choose Kruskal's over Prim's algorithm for MST. 2. If the greedy solution does not give the MST, then is the graph really undirected? And if the graph is not undirected, how would you solve the more generalized MST algorithm: while tree does not form a spanning tree, find an edge that is safe for the tree and add it to the tree.

    Can you modify Prim's for the later?

    I would post more details, but the platform asks us not to post solutions...

  • valerius1001
     + 0 comments

    What is wrong with mys solution - ? public static int kruskals(int gNodes, List gFrom, List gTo, List gWeight) { var edges = new List>(); for (int i = 0; i < gFrom.Count; i++) { edges.Add(new Tuple(gFrom[i], gTo[i], gWeight[i])); }

    edges = edges
    .OrderBy(e => e.Item3)
    .ThenBy(e => e.Item1)
    .ToList();

var visitedNodes = new HashSet<int>();
var mstEdges = new List<Tuple<int, int, int>>();
for (int i = 0; i < edges.Count; i++)
{
    if (!visitedNodes.Contains(edges[i].Item2))
    {
        mstEdges.Add(edges[i]);
        visitedNodes.Add(edges[i].Item2);
    }
    if (mstEdges.Count == gNodes - 1)
        break;
}

var totalWeight = mstEdges.Sum(e => e.Item3);
return totalWeight;

    }

  • 38kbu2pa
     + 0 comments

    VoIP technology is continuously evolving, with ongoing advancements in features, capabilities, and integration options. Providers are constantly innovating to incorporate emerging technologies such as Artificial Intelligence (AI), machine learning, and advanced analytics into their VoIP systems. This commitment to innovation ensures that VoIP services remain at the forefront of communication technology VoIP Phone Services, offering businesses and individuals access to the latest tools and solutions to stay competitive and adapt to future developments.

  • ihorfinance
     + 0 comments

    C++ (more at https://github.com/IhorVodko/Hackerrank_solutions/tree/master , feel free to give a star:) )

    bool areNodesInTheSameTree(
    vector<bool> const & nodesVisited,
    std::unordered_map<int, vector<int>> const & nodeToNeighbours,
    int const nodeA,
    int const nodeB,
    int const nodesCount
){
    using namespace std;
    if(!(nodesVisited.at(nodeA) && nodesVisited.at(nodeB))){
        return false;
    }
    auto nodesVisitedBfs{vector<bool>(nodesCount + 1, false)};
    auto qBfs{queue<int>{}};
    qBfs.push(nodeA);
    nodesVisitedBfs.at(nodeA) = true;
    auto nodeCurrent{qBfs.front()};
    while(!qBfs.empty()){
        nodeCurrent = qBfs.front();
        qBfs.pop();
        for(auto const nodeNext: nodeToNeighbours.at(nodeCurrent)){
            if(nodeNext == nodeB){
                return true;
            }
            if(nodesVisitedBfs.at(nodeNext)){
                continue;
            }
            qBfs.push(nodeNext);
            nodesVisitedBfs.at(nodeNext) = true;
        }
    }
    return false;
}

int kruskals(
    int const nodesCount,
    std::vector<int> const & nodesFrom,
    std::vector<int> const & nodesTo,
    std::vector<int> const & edgeWeightes
){
    using namespace  std;
    auto weightToEdges{multimap<int, pair<int, int>>{}};
    for(size_t idx{0}; idx != edgeWeightes.size(); ++idx){
        weightToEdges.insert({edgeWeightes.at(idx), {nodesFrom.at(idx),
            nodesTo.at(idx)}});
    }
    cout << weightToEdges.size() << '\n';
    auto nodeToNeighbours{unordered_map<int, vector<int>>{}};
    auto weightSubtree{0};
    auto nodesVisited{vector<bool>(nodesCount + 1, false)};
    for(auto const & [weight, edge]: weightToEdges){
        if(::areNodesInTheSameTree(nodesVisited, nodeToNeighbours, edge.first,
            edge.second, nodesCount)
        ){
            continue;
        }
        nodeToNeighbours[edge.first].emplace_back(edge.second);
        nodeToNeighbours[edge.second].emplace_back(edge.first);
        nodesVisited.at(edge.first) = true;
        nodesVisited.at(edge.second) = true;
        weightSubtree += weight;
    }
    return weightSubtree;
}

  • Xuan_HoanG
     + 0 comments

    My python solution

    def kruskals(g_nodes, g_from, g_to, g_weight):
    edges = sorted(zip(g_from, g_to, g_weight), key=lambda x: x[2])
    mst = {}
    cost = 0
    for c, (u, v, w) in enumerate(edges):
        d = {}
        for idx, conn in mst.items():
            if (u in conn):
                d[u] = idx
            if (v in conn):
                d[v] = idx
        if d.get(u, -1) != d.get(v, -2):
            cost += w
    return cost
            mst[c] = mst.pop(d.get(u, -1), set([u])) | mst.pop(d.get(v, -1), set([v]))
        
    return cost

`