Once upon a time, in a kingdom far, far away, there lived a king Byteasar II. There was nothing special neither about him, nor about his kingdom. As a mediocre ruler, he did nothing about his kingdom and preferred hunting and feasting over doing anything about his kingdom prosperity.
Luckily, his adviser, wise magician Bitlin, was working for the kingdom welfare daily and nightly. However, since there was no one to advise him, he completely forgot about one important thing: the roads. Over the years most of the two-way roads built by Byteasar II predecessors were forgotten and no longer traversable. Only a few
roads can still be used.
Bitlin wanted each pair of cities to be connected, but couldn’t find a way to figure out which roads are missing. Desperate, he turned to his magic crystal, seeking help. The crystal showed him a programmer from the distant future: you! Now you’re the only one who can save the kingdom. Given the existing
roads and the number of
cities in the kingdom, you should use the most modern technologies and find out what roads should be built again to make each pair of cities connected. Since the magic crystal is quite old and meticulous, it will only transfer the information that is sorted properly.
The roads to be built should be returned in an array sorted lexicographically, with each road stored as
[cityi, cityj], where
cityi < cityj.
cities = 4 and
roads = [[0, 1], [1, 2], [2, 0]],
the output should be
roadsBuilding(cities, roads) = [[0, 3], [1, 3], [2, 3]].
See the image below: the existing roads are colored black, and the ones to be built are colored red.
- [time limit] 4000ms (py)
- [input] integer citiesThe number of cities in the kingdom.
1 ≤ cities ≤ 100.
- [input] array.array.integer roadsArray of roads in the kingdom. Each road is given as a pair
[cityi, cityj], where
0 ≤ cityi, cityj < citiesand
cityi ≠cityj. It is guaranteed that no road is given twice.
0 ≤ roads.length ≤ 5000,
roads[i].length = 2,
0 ≤ roads[i][j] < cities.
- [output] array.array.integerA unique array of roads that should be built sorted as described above. There’s no need to build loop roads, i.e. roads from a city to itself.
Basic graph knowledge. (Adjacency Matrix)
The rows are the sources of the edges. Columns are the targets.
If we have a road from x to y; we have a road from y to x. (Since roads are to both directions.)
If there is no road between two cities, the adj cell for those two will be zero (0).
matrix is symmetric since adj[x][y]=adj[y][x]
therefore, if we want the roads to be lexicographical order, we can select x to be smaller than y in any case. Therefore, just looking at the upper right triangle of the matrix is enough.
append the required roads from x to y into a new array and return.