Finding isolated city using 2D array-CodePudding

I am given a 2D array, where the ID of the City is the index of the outer array and the numbers inside the inner array represent Highways IDs.

List = [[1,2],[4,5,8],[1,2,3],[1,3]]

I am trying to find a city that is isolated, so no highway connects it to another city (all highways in it are unique in the List and only occur once?). In the example above city 1 with [4,5,8] would be isolated, so a call to the function findIsolatedCity(List) should return 1. If no city could be found, the function returns -1.

I tried implementing a solution in pseudocode but all I could come up with is rather inefficient (4 nested loops). Does anyone know a more efficient solution?

function findIsolatedCity(List)

   isolated_city = -1
 
   for city in range(len(List):
 
      highway_count = 0
      list_unique_highways = []

      for highway in List[city]:
         // check if the highway connects to any other city
         for city_2 in range(len(List)):  // iterate over all cities
            for highway_2 in List[city_2]:  // iterate over all highways in other cities
               if highway == highway_2:
                  highway_count  = 1
         if highway_count == 1:
            list_unique_highways.append(highway)
      
     if length(list_) == length(List[city]):
        isolated_city = city
        return isolated_city

   return isolated_city

CodePudding user response：

Based on comment of @user3386109 here is solution in Python:

from collections import Counter

cities = [[1, 2], [4, 5, 8], [1, 2, 3], [1, 3]]


def find_isolated_cities(cities):
    cnt = Counter(h for c in cities for h in c)
    return sum(all(cnt[h] == 1 for h in c) for c in cities)


print(find_isolated_cities(cities))

Prints:

First we construct counter that counts number of each higway in all sublists and then count cities which have all higways of count equal 1.