Kings

INTRODUCTION: A tournament is a directed graph in which there is a single edge that connects every two vertices. If we consider any two vertices, A and B. in a tournament, there exists an edge from A to B or from B to A. To state it in math jargon, a tournament is a complete. directed graph.

     +---+A+---+                      +---->A+---+
     |         |                      |          |
     |         |                      |          |
     v         v                      +          v
     B <------+C                      C<--------+D

In a tournament, you may have vertices that are designated as "Kings". Kings are vertices that can reach any other vertex m. the graph in two or less steps. In this case. a step is a movement from one vertex to another along an edge that connects them.

PROBLEM: Given the vertices and edges of a graph, return a string array containing the names of all "king" vertices. The vertices are described as an array of strings of the names of the vertices. The edges are described by two input string arrays, the "edgesFrom" array and the "edgesTo" array. The edge is directed from the ith element of the "edgesFrom" input array to the ith element of the "edgesTo" input array. Take the elements of these two arrays pairwise to get the edge set. Return the king vertices in alphabetical order.

• The idea:

  • I mapped all the information into a standard adjacency list.

  • Then I iterated through each list, removing all the elements that correspond inside the adjacency list, and the elements within that adjacency list. In the end, if the hash set was empty (one edge also pointed to itself), or the hash set is of size one where it is not itself, it then points to all elements by a least a 2 edges.

vector<char> king_vertices(vector<char> &ar1, vector<char> &ar2) {
    map<char, vector<char>> list;
    unordered_set<char> check_list;
    unordered_set<char> check_list_copy;
    for (int i = 0; i < ar1.size(); i++) {
        auto &found = list.find(ar1.at(i));        
        if (found == list.end()) {
            vector<char> connections;
            connections.push_back(ar2.at(i));
            list.insert({ {ar1.at(i)}, {connections} });
        }
        else {
            found->second.push_back(ar2.at(i));
        }

        // automatically maintains unique elements
        check_list.insert(ar1.at(i));
        check_list.insert(ar2.at(i));
    }

    check_list_copy = check_list;
    vector<char> kings;

    for (auto &i : list) {
        for (auto &j : i.second) {
            check_list.erase(j);
            //second step
            auto &found3 = list.find(j);
            if (found3 != list.end()) {
                for (int k = 0; k < list.find(j)->second.size(); k++) {
                    check_list.erase(list.find(j)->second.at(k));
                }
            }
        }
        // remainder is itself
        if (check_list.size() <= 1) {
            if (check_list.size() == 0 || check_list.find(i.first) != check_list.end()) {
                kings.push_back(i.first);
                check_list = check_list_copy;
            }
        }
        check_list = check_list_copy;
    }
    sort(kings.begin(), kings.end());
    return kings;
}

int main() {
    vector<char> one = { 'A', 'A', 'B' };
    vector<char> two = { 'B', 'C', 'C' };
    print(king_vertices(one, two));

    one = { 'A', 'A', 'A', 'C' };
    two = { 'E', 'B', 'C', 'D' };
    print(king_vertices(one, two));

    one = { 'A', 'A', 'A','B', 'D', 'D', 'D', 'C' };
    two = { 'B', 'C', 'E','A', 'B', 'C', 'E', 'D' };
    print(king_vertices(one, two));
}