Как найти последний Egde соединяющих вершины из обхода два непересекающихся, equinumerous множества вершин

Question

Учитывая два непересекающиеся, equinumerous (размера n) множество (называемые 0 и 1) со значениями от 1 к 2n я должен найти последний край (пара вершин), образованных определенным обходом.

Прослеживание алгоритм:

• начало от значения 1 (не имеет значения, в котором установлено это значение)
• соединить ее с первой, величиной свободной от противоположного множества (первого по отношению к фактическому значению, так если текущее значение равно 3, то я буду проверять 4, 5, 6, 7, ..., 2n - 1, 2n, 1, 2)
• повторите второй шаг

Пример:

n = 5 
Set "0": { 1, 2, 4, 8, 9 } 
Set "1": { 3, 5, 6, 7, 10 } 

Traversal path: 
1 -> 3 -> 4 -> 5 -> 8 -> 10 -> 2 -> 6 -> 9 -> 7 

Answer -> 9 and 7 

я смог решить эту проблему с 2 * (1 + 2 ... + n) = 0(n^2) сложности. Но я считаю, что есть лучшее решение.

Answer 1

Вы можете сделать это в O(nlogn)

• первого рода как массив и установить current = 1
• Теперь найти какой массив содержит 1, как вы должны начать со значением 1
• Теперь поиск положение current value в противоположном массиве (рядом) с использованием двоичного поиска в O (logn)
• Найдите разницу между близкими значениями слева и справа и измените текущее значение на значение, которое дает наименьшую разницу
• Конечно, установите все значения, с которыми вы уже работали. Так что вы не в два раза работать с тем же значением
• Таким образом, общая сложность O (NlogN)

четвёртую шаг Разработка:

Предположим, что текущее значение в array a и вы поиск в array b ...

current value = 5 
b = { 2 , 3 , 8 , 10} 
      ^

если вы бинарный поиск в массиве b, позиция, которую вы получите, равна 2. Итак, теперь -

current value = 8 и отметьте 8 по мере посещения.
Теперь сделайте step 2 and 3 в array a и так далее ...

Update:

Образец C++ реализация:

#include <bits/stdc++.h> 
using namespace std; 

vector<int>right_a,right_b; 
// Using union_find algorithm to find the next available value(which is not visited) 
int find1(int x) 
{ 
    if(x==right_a[x]) 
     return x; 
    right_a[x]=find1(right_a[x]); 
} 
int find2(int x) 
{ 
    if(x==right_b[x]) 
     return x; 
    right_b[x]=find2(right_b[x]); 
} 
int main() 
{ 
    int i,j,k,l,m,n=5; 

    int a[]={1, 2, 4, 8, 9}; 
    int b[]={3, 5, 6, 7, 10}; 

    for(i=0;i<n;i++) 
    { 
     right_a.push_back(i); 
     right_b.push_back(i); 
    } 

    int cur=1,work_with; 
    if(a[0]==cur) 
    { 
     right_a[0]=1; 
     work_with=0; 
    } 
    else 
    { 
     right_b[0]=1; 
     work_with=1; 
    } 

    printf("%d",1); 
    int cnt=1; 
    while(cnt<2*n) 
    { 
     if(work_with==0) 
     { 
      // find first relative to actual value in array b 
      int ind=lower_bound(b,b+n,cur)-b; 
      if(ind==n) 
       ind=0; 
      ind=find2(ind); 
      int next=ind+1; 
      if(next==n) 
       next=0; 
      right_b[ind]=right_b[next]; // making current value visited 
      printf(" -> %d",b[ind]); 
      cur=b[ind]; 

      work_with=1; 
     } 
     else 
     { 
      // find first relative to actual value in array a 
      int ind=lower_bound(a,a+n,cur)-a; 
      if(ind==n) 
       ind=0; 
      ind=find1(ind); 
      int next=ind+1; 
      if(next==n) 
       next=0; 
      right_a[ind]=right_a[next]; // making current value visited 
      printf(" -> %d",a[ind]); 
      cur=a[ind]; 

      work_with=0; 
     } 
     cnt++; 
    } 
    printf("\n"); 
return 0; 
}