유니온 찾기 알고리즘 구현

Question

일련의 키 값 쌍이 있습니다. 각 키에는 2 개의 값이 있습니다. 키의 값은 일치 할 수 있습니다. 처음에는 Key1, ValueKey1로 시작하고 ValueKey2는 집합 (어쩌면 배열)에 저장됩니다.

이제 각 연속 Keyi에 대해 Valuei와 Valuei + 1이 세트에 있는지 확인합니다. 그들 중 하나가 세트에 있다면 세트에 가입하십시오.

그렇지 않으면 두 KeyValues가 세트에있는 경우 해당 키를 버립니다.

C++을 사용하여이 기능을 구현하는 방법은 거의 없으므로 가능한 경우 코드 스 니펫이나 힌트가 도움이 될 것입니다.

Answer 1

'알고리즘은 C++'(Sedgewick, 3rd ed.)에 의해 사용되었거나 소지하고 계십니까?

이 책에서 발견되는 첫 번째 문제점은 연결성 (7 페이지)이며, 거기에는 쌍을 이룬 조합 찾기 (빠른 조합, 빨리 찾기, 가중치 등) 알고리즘의 여러 구현이 있습니다. 열쇠.

다음은 빠른 찾기 버전입니다 (이 책에서 단지 재 타입 -하지 테스트)

#include <iostream> 
const int N = 10000; 
int main() { 
    int i, p, q, id[N]; 
    for(i = 0; i < N; i++) id[i] = i; 
    while(cin >> p >> q) { 
     int t = id[p]; 
     if (t = id[q]) continue; 
     for (i = 0; i < N; i++) 
      if (id[i] == t) id[i] = id[q]; 
     cout << " " << p << " " << q << endl; 
    } 
} 

그냥 당신은 아마에 반전 수있는 연결되지 않은 쌍 (뱉어 유지 당신이 원하는 것을 얻으십시오)

이 책은 어떻게 작동하는지에 대한 아주 상세한 설명을 가지고 있습니다. 그리고 나는 당신이 그것을 가지고 있다고 생각합니다.