온라인 판사의 문제를 해결하려고했습니다. 초기에 에지가없는 n 개의 정점 그래프 (< = 50000)가 주어지면, m 개의 에지 (< 100000)가 주어지며 각각의 추가 후에 bridges의 수를 출력하라는 요청을 받았습니다. 기한은 2 초입니다. O (N + M)에서 실행되는 브리지 찾기 알고리즘과 예측 가능한 O (M * (N + M)) 시간을 예측할 수 있습니다. 누군가 적절한 알고리즘을 도와 주시겠습니까?그래프에서 브리지를 점진적으로 계산합니다.
감사합니다.
섬은 노드를 모아 놓은 것으로, 어떤 교량을 교차하지 않고도 한 노드에서 다른 노드로 이동할 수 있습니다. 다른 노드에 연결되지 않은 단일 노드는 아일랜드입니다.
섬 사슬은 교량으로 연결된 일련의 섬입니다. 섬 사슬은 비순환 적이다; 당신이 다리를 통해 섬을 떠날 경우 같은 다리를 제외하고는 섬으로 돌아갈 수 없습니다. 이것은 섬 체인을 구성하는 노드들의 집합이 비순환 적이라고 말하는 것과 같지 않습니다. 개별 섬에는 사이클이있을 수 있습니다.
그래프에 가장자리를 추가 할 때, 당신의 체인, 섬, 교량을 추적하기 위해 이러한 규칙을 따르 새로운 에지가 자신에게 섬을 연결하는 추가하면
는, 그 가장자리는다리가 아닙니다. 총 교량 수는 변경되지 않습니다.
두 개의 섬이 같은 섬 체인에 속하지 않고 그 둘을 연결하는 새로운 가장자리가 추가되면 해당 가장자리가 다리가되어 두 섬 체인이 단일 섬 체인으로 병합됩니다.
두 개의 섬이 섬 체인의 일부이고 이들을 연결하는 새로운 가장자리가 추가되면 일부 섬을 병합하여 acyclic 속성을 유지해야합니다. 두 섬을 연결하는 섬 체인을 통과하는 경로를 찾습니다. 이 두 섬을 포함하여이 길을 가로 지르는 섬 전체를 단일 섬으로 합치십시오. 이런 식으로 트래버스하는 모든 다리는 교량이되지 않습니다.
이러한 단계를 사용하면 가장자리에 가장자리를 추가 할 때 그래프에 브리지 수를 유지할 수 있습니다. 연결되지 않은 노드 그래프로 시작하십시오. 각 노드는 단일 노드를 포함하는 단일 아일랜드를 포함하는 아일랜드 체인입니다. 가장자리를 추가 할 때 위의 세 가지 규칙을 참조하여 필요에 따라 섬과 섬 체인을 병합하십시오.
아일랜드는 노드 집합으로 표현할 수 있으며 아일랜드 체인은 섬의 비순환 식 비순환 그래프로 나타낼 수 있습니다. 알고리즘의 가장 비싼 부분은 기존의 두 섬 사이의 경로를 찾는 것입니다. 직관적으로, 체인의 섬의 수는 n에 비해 작기 때문에 총 복잡성은 O (m) 시간에 가깝게 유지됩니다.
예. 이제는 멍청한 것 같아. 귀하의 아이디어는 그 시간 내에 달성 가능한 것 같습니다. 나는 코드를 작성하고 돌아올거야. 감사!! – frodo