하나의 edgeList를 사용하는 n개의 노드가 있는 하나의 무방향 가중치 그래프가 있다고 가정합니다. 여기서 edgeList[i]에는 3개의 매개변수(u, v, w)가 있으며 거리가 w인 u에서 v까지의 경로가 있음을 나타냅니다. 또한 query[i]에 (p, q, lim)이 있는 또 다른 쿼리 배열이 있습니다. 이 쿼리는 거리가 lim보다 작은 p에서 q까지의 경로(직접 또는 다른 노드를 통한)가 있는지 묻습니다. 각 쿼리에 대해 True/False 결과를 포함하는 배열을 반환해야 합니다.
따라서 입력이 다음과 같으면
그러면 출력은 [True, False, True]가 됩니다. 1에서 4로 이동하려면 1 -> 3 -> 4 경로를 비용 11로 따를 수 있기 때문에 두 번째 경로는 3 미만을 사용하여 2에서 3으로 이동할 수 없기 때문에 거짓이고 마지막 경로는 1에서 갈 수 있기 때문에 참입니다. 경로 1 -> 3 -> 2를 사용하여 2로, 비용은 14, 15 미만입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
parent :=0에서 n까지의 목록
-
rank :=크기가 n+1이고 0으로 채워진 목록
-
find() 함수를 정의합니다. 상위 x
가 필요합니다. -
부모[x]가 x와 같으면
-
x를 반환
-
-
부모[x] :=찾기(부모, 부모[x])
-
부모 반환[x]
-
함수 union()을 정의합니다. 부모, b
-
a :=찾기(부모, a)
-
b :=찾기(부모, b)
-
b와 같으면
-
반환
-
-
순위[a] <순위[b]이면
-
부모[a] :=b
-
-
그렇지 않으면 rank[a]> rank[b]일 때
-
부모[b] :=a
-
-
그렇지 않으면
-
부모[b] :=a
-
순위[a] :=순위[a] + 1
-
-
주요 방법에서 다음을 수행하십시오 -
-
가중치 매개변수를 기반으로 edgeList 정렬
-
res :=쿼리 수가 0으로 채워진 배열
-
쿼리 :=쿼리의 각 인덱스 i 및 값 ch에 대한 쌍(i, ch) 목록
-
제한 매개변수를 기반으로 쿼리 정렬
-
인드 :=0
-
쿼리의 각 인덱스 i 트리플렛(a, b, w)에 대해 수행
-
동안 ind
-
공용체(부모, edgeList[ind, 0])
-
인드 :=인드 + 1
-
-
res[i] :=find(parent, a)는 find(parent, b)와 동일합니다.
-
-
반환 해상도
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
def solve(n, edgeList, queries):
parent = [i for i in range(n+1)]
rank = [0 for i in range(n+1)]
def find(parent, x):
if parent[x] == x:
return x
parent[x] = find(parent, parent[x])
return parent[x]
def union(parent, a, b):
a = find(parent, a)
b = find(parent, b)
if a == b:
return
if rank[a] < rank[b]:
parent[a] = b
elif rank[a] > rank[b]:
parent[b] = a
else:
parent[b] = a
rank[a] += 1
edgeList.sort(key = lambda x: x[2])
res = [0] * len(queries)
queries = [[i, ch] for i, ch in enumerate(queries)]
queries.sort(key = lambda x: x[1][2])
ind = 0
for i, (a, b, w) in queries:
while ind < len(edgeList) and edgeList[ind][2] < w:
union(parent, edgeList[ind][0], edgeList[ind][1])
ind += 1
res[i] = find(parent, a) == find(parent, b)
return res
n = 4
edgeList = [(1,2,16),(1,3,8),(2,4,3),(2,3,6),(4,3,3),]
queries = [(1,4,12),(2,3,3),(1,2,15)]
print(solve(n, edgeList, queries)) 입력
4, [(1,2,16),(1,3,8),(2,4,3),(2,3,6),(4,3,3)],[(1,4,12),(2,3,3),(1,2,15)]
출력
[True, False, True]