from typing import List
from typing import Set


def _reconstruct_set_from_weights(weights: List[int]) -> Set[int]:
    """
    Method that uses the auxiliary array of weights to reconstruct the maximum independent set. It compare the
    weighted matrix iteratively starting for the last vertex of the graph.
    The algorithm is the next:

    * If the weighted sum of the set with vertex :math:`i` is different than the weighted sum of the set
      without the vertex, the vertex is added to the set and the previous one is skipped.
    * Else, the vertex is not added and the previous vertex is analyze

    :param weights: auxiliary array with the weighted sum
    :return: a set with the indices of the vertices that form the maximum independent set
    """
    vertex_index = len(weights) - 1
    max_independent_set = set()
    while vertex_index >= 1:
        if weights[vertex_index] != weights[vertex_index - 1]:
            max_independent_set.add(vertex_index)
            vertex_index -= 2
        else:
            vertex_index -= 1
    # If the second vertex is not in the set, add the first
    if not max_independent_set.__contains__(1):
        max_independent_set.add(0)
    return max_independent_set