一道graph面经题讨论

Macy204 发表于 2021-10-3 00:10
请问楼主这是什么岗位？NG吗？

在职跳槽 zszszszszs
senior or lead 根据表现定。

我的方法是：连接所有边权小于thredhold的，然后计算出最大连通块的个数。

我寫的solution，但是不保證城市都會連再一起

1. """
   
2. Takes list of correlation pairs as input, pair: ['city1', 'city2', correlation]
   
3. Return two graph, one representing the valid cities to put together,
   
4. the other one is the cities that cannot be put together.
   
5. """
   
6. def buildGraph(correlationPairs, threshold):
   
7.         validCities = set()
   
8.         invalidPairs = {}
   
9. 
   
10.         for pair in correlationPairs:
    
11.                 city1, city2, correlation = pair[0], pair[1], pair[2]
    
12.                 if correlation > threshold:
    
13.                         if city1 not in invalidPairs:
    
14.                                 invalidPairs[city1] = set()
    
15.                         if city2 not in invalidPairs:
    
16.                                 invalidPairs[city2] = set()
    
17.                         invalidPairs[city1].add(city2)
    
18.                         invalidPairs[city2].add(city1)
    
19. 
    
20.         for pair in correlationPairs:
    
21.                 city1, city2, correlation = pair[0], pair[1], pair[2]
    
22.                 if city1 not in invalidPairs:
    
23.                         validCities.add(city1)
    
24.                 if city2 not in invalidPairs:
    
25.                         validCities.add(city2)
    
26. 
    
27.         return validCities, invalidPairs
    
28. 
    
29. def dfs(combination, invalidPairs, invalidCities, addedCities, start):
    
30.         if start == len(invalidCities):
    
31.                 if len(addedCities) > len(combination):
    
32.                         for value in combination:
    
33.                                 combination.remove(value)
    
34.                         for value in addedCities:
    
35.                                 combination.add(value)
    
36.                         print("combination: ", combination)
    
37.                 return
    
38. 
    
39.         for i in range(start, len(invalidCities)):
    
40.                 addable = True
    
41.                 for neighbor in invalidPairs[invalidCities[i]]:
    
42.                         if neighbor in addedCities:
    
43.                                 addable = False
    
44.                                 break
    
45.                 if addable:
    
46.                         addedCities.add(invalidCities[i])
    
47.                         dfs(combination, invalidPairs, invalidCities, addedCities, i+1)
    
48.                         addedCities.remove(invalidCities[i])
    
49. 
    
50. def getMostCities(correlationPairs, threshold):
    
51.         validCities, invalidPairs = buildGraph(correlationPairs, threshold)
    
52.         invalidCities = list(invalidPairs)
    
53.         invalidCities.sort()
    
54.         print("invalidCities: ", invalidCities)
    
55.         combination = set()
    
56.         dfs(combination, invalidPairs, invalidCities, set(), 0)
    
57.         return validCities.union(combination)
    
58. 
    
59. if __name__ == "__main__":
    
60.         correlations = [['a', 'b', 1], ['a', 'c', 1], ['b', 'c', 1], ['b', 'd', 2], ['c', 'e', 2]]
    
61.         cities = getMostCities(correlations, 1.5)
    
62.         print("cities: ", cities)
    

复制代码

看要求，全联通的几个city才可以是一个城市组合，比如，(a, b, 1), (c, d, 1), (b, c, 1,), (a, d, 1), (a, c, 2), (b, d, 1) threadhold=1.5有几个组合方式

1. [a], [b], [c], [d]
   
2. [a], [c], [b, d]
   
3. [a], [b], [c, d]
   
4. [a], [d], [b, c]
   
5. [b], [c], [a, d]
   
6. [c], [d], [a, b]
   
7. [a, b], [c, d]
   
8. [b, c], [a, d]
   
9. [a, b, d], [c]
   
10. [a], [b, c, d]

复制代码

因为有(a, c, 2)和threshold=1.5，a和c不能在一个group，确定不是一个permutation的问题？
逆向考虑的话，所有的不连通的edge和above threshold的edge都是排除某一个组合的条件所以是比较重要的信息。

“找出最多的城市组合”这个题意需要clarify一下，可以是最大化城市群，也可以是找到所有组合。但是最大化的话，输出结果不唯一。 看我的例子
[a, b, d], [c]
[a], [b, c, d]