Hackerrank Problem Solving (Intermediate) Certificate Q2

Hotel Construction

Description:

There are a certain number of cities in a country, some of which are connected with bidirectional roads. The number of roads is one less the number of cities, and it is possible to travel between any pair of of cities using the roads. The distance between cities is the minimum number of roads one has to cross when traveling between them. How many ways are there to build exactly 3 hotels, each in a different city, such that the distance between every pair of hotels is equal?

For example, let’s say there are n = 5 cities, and roads = [[1, 2], [1, 3], [1, 4], [1, 5]]. This means that city 1 is connected with roads to all other cities. (no picture here)

There are 4 ways to build exactly 3 hotels, each in a different city, so that the distance between every pair of hotels is equal:

1. Build hotels in cities 2, 3 and 4.
2. Build hotels in cities 2, 3 and 5.
3. Build hotels in cities 2, 4 and 5.
4. Build hotels in cities 3, 4 and 5.

Solution (C++)

Before Coding

1. The graph is acyclic and connected, and there is only one way for every pair of cities.
2. Find the triplet that: take one node as the root node and other two as chidren, then compare and depth search them by increasing the distance(i.e. if the grandchildren fit the condition)

int count(int a, int b, int c, int na, int nb, int nc, map<int, vector<int>>& conn) {
    if (1 == conn[a].size() || 1 == conn[b].size() || 1 == conn[c].size()) {
        return 0;
    }
    int cnt = (conn[a].size() - 1) * (conn[b].size() - 1) * (conn[c].size() - 1);
    
    for (int i = 0; i < conn[a].size(); i++) {
        if (conn[a][i] != na)
        for (int j = 0; j < conn[b].size(); j++) {
            if (conn[b][j] != nb)
            for (int k = 0; k < conn[c].size(); k++) {
                if (conn[c][k] != nc) {
                    cnt += count(conn[a][i], conn[b][j], conn[c][k], 
                        a, b, c, conn);
                }
            }
        }
    }
    
    return cnt;
}
int numberOfWays(vector<vector<int>> roads) {
    // acyclic graph
    int ans = 0;
    map<int, vector<int>> conns;
    
    // build connection map
    for (auto& road : roads) {
        conns[road[0]].push_back(road[1]);
        conns[road[1]].push_back(road[0]);
    }
    // for each node as a star
    for (auto& conn : conns) {
        // loop through 3 nodes
        auto& nodes = conn.second;
        auto star = conn.first;
        
        for (int i = 0; i < nodes.size(); i++) {
            for (int j = i + 1; j < nodes.size(); j++) {
                for (int k = j + 1; k < nodes.size(); k++) {
                    // for nodes i, j, k, there will be no loop
                    ans++;
                    ans += count(nodes[i], nodes[j], nodes[k], star, star, star, conns);
                }
            }
        }
    }
    
    return ans;
}