n개의 도시가 있고 이들 도시를 연결하는 도로가 있다고 가정합니다. 각 도로[i] =[u, v]는 도시 u와 v 사이에 양방향 도로가 있음을 나타냅니다. 이제 네트워크 순위는 각 도시에 직접 연결된 도로의 총 수입니다. 도로가 두 도시와 직접 연결되어 있는 경우에는 한 번만 계산됩니다. 그리고 네트워크의 최대 네트워크 순위는 다른 도시의 모든 쌍의 최대 네트워크 순위입니다. 따라서 다른 도로가 있는 경우 전체 네트워크의 최대 네트워크 순위를 찾아야 합니다.
따라서 입력이 다음과 같으면
도시 1과 2를 연결하는 5가지 다른 방법이 있기 때문에 출력은 5가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- n :=노드 수
- s :=새로운 세트
- d :=지도, 일부 키가 없으면 0 반환
- 도로의 각 모서리(x,y)에 대해 다음을 수행합니다.
- d[x] :=d[x] + 1
- d[y] :=d[y] + 1
- d에 쌍(x,y) 삽입
- ans :=0
- l :=범위 0에서 n까지의 새 목록
- 노드 번호를 기준으로 내림차순으로 l 정렬
- 임계값:=d[l[0]] 및 d[l[1]]의 최소값
- 0에서 l - 1 사이의 범위에 있는 i에 대해
- i+1에서 l - 1까지의 범위에 있는 j에 대해
- d[l[j]] <임계값이면
- 루프에서 나오다
- 커:=d[l[i]] + d[l[j]]
- (l[i],l[j])가 s에 있거나 (l[j],l[i])가 s에 있으면
- curr :=curr - 1
- ans :=ans 및 curr의 최대값
- d[l[j]] <임계값이면
- i+1에서 l - 1까지의 범위에 있는 j에 대해
- 반환
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
from collections import defaultdict def solve(roads): nodes = set() s = set() d = defaultdict(int) for x,y in roads: nodes.update([x,y]) d[x]+=1 d[y]+=1 s.add((x,y)) ans = 0 n = len(nodes) l = list(range(n)) l.sort(key=lambda x:d[x], reverse = True) threshold = min(d[l[0]],d[l[1]]) for i in range(len(l)-1): for j in range(i+1,len(l)): if d[l[j]]<threshold: break curr = d[l[i]]+d[l[j]] if (l[i],l[j]) in s or (l[j],l[i]) in s: curr-=1 ans = max(ans,curr) return ans roads = [(0,1),(0,3),(1,2),(1,3),(2,3),(2,4)] print(solve(roads))
입력
[(0,1),(0,3),(1,2),(1,3),(2,3),(2,4)]
출력
5