Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cstdlib> // для функций rand() и srand()
- #include <list>
- using namespace std;
- const int p = 2000000033;
- int rand_int(int min, int max)
- {
- static const double fraction = 1.0 / (static_cast<double>(RAND_MAX) + 1.0);
- // Равномерно распределяем рандомное число в нашем диапазоне
- return static_cast<int>(rand() * fraction * (max - min + 1) + min);
- }
- int uni_hash(int a, int b, int k)
- {
- return a * k + b;
- }
- int main()
- {
- srand(4541);
- int n, a, b;
- int alpha_k, beta_k;
- cin >> n;
- const int m = 3 * n;
- vector<int> A(m); //Массив меток (i-я ячейка хранит число которое стоит над вершиной i)
- vector<int> K(n); //Массив ключей
- for (int i = 0; i < n; ++i)
- cin >> K[i];
- bool flag = True;
- while (flag)
- {
- Graph g(m);
- a1 = rand_int(1, p - 1);
- b1 = rand_int(0, p - 1);
- a2 = rand_int(1, p - 1);
- b2 = rand_int(0, p - 1);
- for (int i = 0; i < n; ++i)
- {
- alpha_k = uni_hash(a1, b1, K[i]);
- beta_k = uni_hash(a2, b2, K[i]);
- g.addEdge(alpha_k, beta_k);
- }
- //Граф построен, осталось проверить что он корректный. Вызову DFS и он ответит yes or no
- if (!Graph.DFS())
- {
- flag = true; //Граф некоррек, придется делать по новой
- }
- else
- {
- flag = false; //Граф корректен, выходим из while
- }
- }
- //Массив А заполнен, можно заполнить хэш таблицу используя построенную ХФ
- int idx;
- vector<int> set(m);
- for (int i = 0; i < n; ++i)
- {
- idx = (A[uni_hash(a1, b1, K[i])] + A[uni_hash(a2, b2, K[i])]) % m;
- set[idx] = K[i];
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment