Cerinta completa

Given an undirected weighted connected graph, find the Really Special SubTree in it. The Really Special SubTree is defined as a subgraph consisting of all the nodes in the graph and:

  • There is only one exclusive path from a node to every other node.
  • The subgraph is of minimum overall weight (sum of all edges) among all such subgraphs.
  • No cycles are formed

To create the Really Special SubTree, always pick the edge with smallest weight. Determine if including it will create a cycle. If so, ignore the edge. If there are edges of equal weight available:

  • Choose the edge that minimizes the sum where and are vertices and is the edge weight.
  • If there is still a collision, choose any of them.

Print the overall weight of the tree formed using the rules.

For example, given the following edges:

u	v	wt
1	2	2
2	3	3
3	1	5

First choose at weight . Next choose at weight . All nodes are connected without cycles for a total weight of .

Function Description

Complete the function in the editor below. It should return an integer that represents the total weight of the subtree formed.

kruskals has the following parameters:

  • g_nodes: an integer that represents the number of nodes in the tree
  • g_from: an array of integers that represent beginning edge node numbers
  • g_to: an array of integers that represent ending edge node numbers
  • g_weight: an array of integers that represent the weights of each edge

Input Format

The first line has two space-separated integers and , the number of nodes and edges in the graph.

The next lines each consist of three space-separated integers , and , where and denote the two nodes between which the undirected edge exists and denotes the weight of that edge.

Constraints

**Note: ** If there are edges between the same pair of nodes with different weights, they are to be considered as is, like multiple edges.

Output Format

Print a single integer denoting the total weight of the Really Special SubTree.

Limbajul de programare folosit: java8

Cod:

import java.io.*;
import java.util.*;

class Edge implements Comparable<Edge> {
    private int _x;
    private int _y;
    private double _w;

    public Edge(int x, int y, double w) {
        this._x = x;
        this._y = y;
        this._w = w;
    }

    public int getX() {
        return this._x;
    }

    public int getY() {
        return this._y;
    }

    public double getW() {
        return this._w;
    }

    public int compareTo(Edge b) {
        if (this._w < b._w) {
            return -1;
        } else if (this._w > b._w) {
            return 1;
        } else {
            if (this._x + this._y + this._w < b._x + b._y + b._w) {
                return -1;
            } else if (this._x + this._y + this._w > b._x + b._y + b._w) {
                return 1;
            }
        }
        return 0;
    }
}

class Node {
    private int _id;
    private HashSet<Integer> _members = new HashSet<Integer>();

    Node(int id) {
        this._id = id;
        this._members.add(this._id);
    }

    public int getId() {
        return this._id;
    }

    public void setMembers(HashSet<Integer> m) {
        this._members = m;
    }

    public HashSet<Integer> getMembers() {
        return this._members;
    }

    public boolean hasMember(Integer id) {
        return this._members.contains(id);
    }
}

public class Solution {

    public static void main(String[] args) {
        ArrayList<Edge> edges = new ArrayList<Edge>();
        ArrayList<Node> nodes = new ArrayList<Node>();
        ArrayList<Edge> path = new ArrayList<Edge>();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int e = sc.nextInt();

        for (int i = 1; i <= n; i++) {
            nodes.add(new Node(i));
        }

        for (int i = 0; i < e; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            int w = sc.nextInt();

            Edge tmp = new Edge(x, y, w);
            edges.add(tmp);
        }

        Collections.sort(edges);

        for (int i = 0; i < edges.size(); i++) {
            Edge tmp = edges.get(i);
            int indexX = tmp.getX()-1;
            int indexY = tmp.getY()-1;

            Node x = nodes.get(indexX);
            Node y = nodes.get(indexY);

            if (!x.hasMember(y.getId())) {
                path.add(tmp);

                HashSet<Integer> m = x.getMembers();
                m.addAll(y.getMembers());

                Iterator<Integer> iterator = m.iterator();
                while (iterator.hasNext()) {
                    Integer current = iterator.next();
                    nodes.get(current-1).setMembers(m);
                }
            }
        }

        int sum = 0;
        for (int i = 0; i < path.size(); i++) {
            sum += path.get(i).getW();
        }
        System.out.println(sum);
    }
}

Scor obtinut: 1.0

Submission ID: 464604256

Link challenge: https://www.hackerrank.com/challenges/kruskalmstrsub/problem

Kruskal (MST): Really Special Subtree