0에서 n - 1까지 번호가 매겨진 n개의 꼭짓점을 포함하는 그래프가 있다고 가정합니다. 그래프는 방향이 없으며 각 모서리에는 가중치가 있습니다. 그래프는 세 가지 유형의 가중치를 가질 수 있으며 각 가중치는 특정 작업을 나타냅니다. 그래프를 횡단할 수 있는 두 사람, 즉 Jack과 Casey가 있습니다. 간선의 가중치가 1인 경우 Jack은 그래프를 순회할 수 있고, 가중치가 2인 경우 Casey는 그래프를 순회할 수 있으며, 간선의 가중치가 3인 경우 둘 다 그래프를 순회할 수 있습니다. 그래프를 둘 다 순회할 수 있도록 하려면 필요한 간선을 제거해야 합니다. 잭과 케이시. 그래프를 순회 가능하게 만들기 위해 제거할 간선의 수를 반환하거나 순회할 수 없는 경우 -1을 반환합니다.
따라서 입력이 다음과 같으면
및 n =5; 그러면 출력은 -1이 됩니다.
간선을 제거하여 그래프를 둘 다 탐색 가능하게 만들 수는 없습니다. 따라서 답은 -1입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
find() 함수를 정의합니다. 이것은 가치가 필요합니다
-
val이 root[val]와 같지 않으면
-
루트[발] :=찾기(루트[발])
-
-
루트 반환[val]
-
-
함수 union()을 정의합니다. val1, val2가 필요합니다.
-
val1:=찾기(val1)
-
val2 :=찾기(val2)
-
val1이 val2와 같으면
-
0 반환
-
-
루트[val1] :=val2
-
1 반환
-
-
해상도 :=0
-
edge1 :=0
-
edge2 :=0
-
root :=범위 0에서 n + 1까지의 새 목록
-
각 모서리(u, v)와 e의 가중치 w에 대해 다음을 수행합니다.
-
u가 3과 같으면
-
Union(v, w)이 0이 아니면
-
edge1 :=edge1 + 1
-
edge2 :=edge2 + 1
-
-
그렇지 않으면
-
해상도 :=해상도 + 1
-
-
-
-
root0 :=root[인덱스 0에서 끝까지]
-
각 모서리(u, v)와 e의 가중치 w에 대해 다음을 수행합니다.
-
u가 1과 같으면
-
Union(v, w)이 0이 아니면
-
edge1 :=edge1 + 1
-
-
그렇지 않으면
-
해상도 :=해상도 + 1
-
-
-
-
루트 :=루트0
-
각 모서리(u, v)와 e의 가중치 w에 대해 다음을 수행합니다.
-
u가 2와 같으면
-
Union(v, w)이 0이 아니면
-
edge2 :=edge2 + 1
-
-
그렇지 않으면
-
해상도 :=해상도 + 1
-
-
-
-
edge1이 edge2와 같으면 res를 반환하고 n - 1
-
그렇지 않으면 -1을 반환합니다.
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다.
def solve(n, e):def find(val):if val !=root[val]:root[val] =find(root[val]) return root[val] def union(val1, val2) :val1, val2 =find(val1), find(val2) if val1 ==val2:return 0 root[val1] =val2 return 1 res =edge1 =edge2 =0 root =list(range(n + 1)) for u , v, w in e:if u ==3:if union(v, w):edge1 +=1 edge2 +=1 else:res +=1 root0 =root[:] for u, v, w in e:if u ==1:if union(v, w):edge1 +=1 else:res +=1 root =root0 for u, v, w in e:if u ==2:if union(v, w):edge2 +=1 else:res +=1 return res if edge1 ==edge2 ==n - 1 else -1print(solve(5, [(0,1,1),(1,2,2),(2, 3,3),(3,4,1),(4,0,2)]))
입력
입력:5, [(0,1,1),(1,2,2),(2,3,3),(3,4,1),(4,0,2)]출력
-1