Advertisement
pasholnahuy

Untitled

Sep 29th, 2023
784
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
JSON 1.92 KB | None | 0 0
  1. #include <algorithm>
  2. #include <chrono>
  3. #include <cmath>
  4. #include <iostream>
  5. #include <random>
  6. #include <vector>
  7. #include <unordered_set>
  8.  
  9. using namespace std;
  10.  
  11. int s;
  12.  
  13. void check(unordered_set<int>& candidates, unordered_set<int>& compsub, unordered_set<int>& not_c, vector<vector<int>>& graph) {
  14.     if (compsub.size() >= s){
  15.         cout << "YES";
  16.         exit(0);
  17.     }
  18.     bool cont = false;
  19.     for (auto el: not_c){
  20.         bool flag = false;
  21.         for (auto c: candidates){
  22.             if (!graph[c][el]){
  23.                 flag = true;
  24.                 break;
  25.             }
  26.         }
  27.         if (!flag){
  28.             cont = true;
  29.             break;
  30.         }
  31.     }
  32.     while (!candidates.empty() && !cont){
  33.         auto v = *candidates.begin();
  34.         compsub.insert(v);
  35.         unordered_set<int> new_candidates;
  36.         unordered_set<int> new_not_c;
  37.         for (auto el: candidates){
  38.             if (!graph[el][v] && v != el){
  39.                 new_candidates.insert(el);
  40.             }
  41.         }
  42.         for (auto el: not_c){
  43.             if (!graph[el][v] && v != el){
  44.                 new_not_c.insert(el);
  45.             }
  46.         }
  47.         if (!new_candidates.empty()){
  48.             check(new_candidates, compsub, new_not_c, graph);
  49.         }
  50.         candidates.erase(v);
  51.         not_c.insert(v);
  52.         compsub.erase(v);
  53.     }
  54.  
  55. }
  56.  
  57. int main() {
  58.     int v, k;
  59.     cin >> v >> k;
  60.     s = k;
  61.     int e;
  62.     cin >> e;
  63.     unordered_set<int> candidates;
  64.     unordered_set<int> compsub;
  65.     unordered_set<int> not_c;
  66.     vector<vector<int>> graph(v, vector<int>(v, true));
  67.     for (int i = 0; i < v; ++i){
  68.         candidates.insert(i);
  69.     }
  70.     for (int i = 0; i < e; ++i) {
  71.         int v1, v2;
  72.         cin >> v1 >> v2, --v1, --v2;
  73.         graph[v1][v2] = false;
  74.         graph[v2][v1] = false;
  75.     }
  76.     check(candidates, compsub, not_c, graph);
  77.     cout << "NO";
  78.     return 0;
  79.  
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement