hpnq

Untitled

Feb 17th, 2024 (edited)
966
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.74 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. //speed coding
  3.  
  4. #define mp make_pair
  5. #define cve(tpy) for (auto i : tpy) {for(auto j : i){cout << j << " ";  }cout << "\n";} ;
  6. #define f first
  7. #define s second
  8. #define loop(i, x, n) for (int i = x; i < n; i++)
  9. #define joop(x, n) for (ll j = x; j < n; j++)
  10. #define lp(n) for (ll i = 0; i < n; i++)
  11. #define err cout << "ERROR" << endl;
  12. #define all(x) x.begin(), x.end()
  13. #define pb push_back
  14. #define sz(x) x.size()
  15. #define rndm rng()
  16.  
  17. // types
  18. #define pii pair<int, int>
  19. #define pll pair<ll, ll>
  20. #define vvi vector<vector<int>>
  21. #define vvll vector<vector<ll>>
  22. typedef long long ll;
  23. typedef long double ld;
  24.  
  25. // types of data
  26. #define inf 1000000000
  27. #define infll 1000000000000000000
  28. #define INF ll(1e18)
  29.  
  30. #define md 998244353
  31. #define mod 1000000009
  32. //#define K 239017
  33.  
  34. #define DEBUG 1
  35. using namespace std;
  36. mt19937_64 rng(113113);
  37. uniform_int_distribution<ll> drist;
  38.  
  39.  
  40. vector<vector<int>> g, inc;
  41. int n, m;
  42.  
  43. void hip_1(int x){
  44.     cout << "1) \n";
  45.     for(auto i : g[x-1]){
  46.         cout << i + 1 << "\n"; // гиперребра дл вершины x
  47.     }
  48. }
  49.  
  50. void ve_2(int u){
  51.     cout << "2)\n";
  52.     loop(i, 0, n){
  53.         for(auto v : g[i]){
  54.             if(u == v+1){
  55.                 cout << i+1 << '\n';
  56.                 continue;
  57.             }
  58.         }
  59.     }
  60. }
  61.  
  62. void dv_hip_3(){
  63.     cout << "3)\n";
  64.     vector<vector<int>> g1;
  65.     g1.resize(m);
  66.     loop(i, 0, n){
  67.         loop(j, 0, m){
  68.             if(inc[i][j]){
  69.                 g1[j].pb(i);
  70.             }
  71.         }
  72.     }
  73.     cve(g1); // выводим наш двойственный гиперграф
  74. }
  75.  
  76. void l4(){
  77.     // ребёрный
  78.     cout << "4)\nedge graph: \n";
  79.     vector<vector<int>> g_1;
  80.     g_1.resize(m);
  81.  
  82.     loop(i, 0, n){
  83.         for(auto j : g[i]){
  84.             for(auto k : g[i]){
  85.                 if(k != j){
  86.                     int skip = 1;
  87.                     for(auto kinj : g_1[j]){
  88.                         if(kinj == k){
  89.                             skip = 0;
  90.                             break; // защита от одинаковых
  91.                         }
  92.                     }
  93.                     if(skip){
  94.                         g_1[j].pb(k);
  95.                     }
  96.                 }
  97.             }
  98.         }
  99.     }
  100.     cve(g_1);
  101.     // вершинный
  102.     cout << "vertex graph: \n";
  103.     vector<vector<int>> g_2;
  104.     g_2.resize(n);
  105.  
  106.     loop(i, 0, n){
  107.         loop(j, 0, n){
  108.             if(j != i){
  109.                 for(auto q : g[i]){
  110.                     for(auto q_1 : g[j]){
  111.                         if(q_1 == q){
  112.                             g_2[i].pb(j); // вершинный гиперграф, получается из того, что две гипервершины имеют один гиперграф.
  113.                         }
  114.                     }
  115.                 }
  116.  
  117.             }
  118.         }
  119.     }
  120.     cve(g_2);
  121.  
  122. }
  123. void l5(){
  124.     cout << "5)\n";
  125.     vector<vector<int>> g_1;
  126.     g_1.resize(n);
  127.     vector<int> v;
  128.     int v_n;
  129.     cin >> v_n;
  130.     v.resize(v_n);
  131.     loop(i, 0, v_n) cin >> v[i];
  132.  
  133.     loop(i, 0, n){
  134.         for(auto q : v){
  135.             if(q - 1 == i){
  136.                 g_1[i] = g[i];
  137.             }
  138.         }
  139.     }
  140.     cve(g_1);
  141. }
  142. void l6(){
  143.     cout << "6)\n";
  144.     vector<vector<int>> g_1;
  145.     vector<int> e;
  146.     int e_n;
  147.     cin >> e_n;
  148.     e.resize(e_n);
  149.     g_1.resize(n);
  150.     loop(i, 0, e_n) cin >> e[i];
  151.  
  152.     loop(i, 0, n){
  153.         int added = 0;
  154.         for(auto ej : g[i]){ // перебираю гиперрёбра вершины
  155.             for(auto k : e){
  156.                 if(k-1 == ej){
  157.                     g_1[i] = g[i];
  158.                     added = 1;
  159.                     break;
  160.                 }
  161.             }
  162.             if(added) break;
  163.         }
  164.     }
  165.     cve(g_1);
  166. }
  167.  
  168. vector<pair<vector<int>, set<int>>> g_1;
  169. vector<bool> used;
  170. bool dfs(int v){
  171.     used[v] = true;
  172.     for(int u : g_1[v].f){
  173.  
  174.         if(!used[u]){
  175.             dfs(u);
  176.             std::vector<int> common_data;
  177.             set_intersection(g_1[v].s.begin(),g_1[v].s.end(),g_1[u].s.begin(),g_1[u].s.end(), std::back_inserter(common_data));
  178. //            err
  179. //            for(auto qq : common_data){
  180. //                cout << qq << " ";
  181. //            }
  182. //            cout << common_data[0] << '\n';
  183.  
  184.             if(!common_data.empty()){ // если пересечение не пустое, то всё круто
  185.                 return true;
  186.             }
  187.             return false;
  188.         }
  189.     }
  190.     return true;
  191. }
  192.  
  193. void s_helly(){
  194.     // ребёрный
  195.     cout << "7) HELLY CONDITION \n";
  196.     g_1.resize(m);
  197.  
  198.     loop(i, 0, n){
  199.         for(auto j : g[i]){
  200.             for(auto k : g[i]){
  201.  
  202.                 if(k != j){
  203.                     int skip = 1;
  204.                     for(auto kinj : g_1[j].f){
  205.                         if(kinj == k){
  206.                             skip = 0;
  207.                             break; // защита от одинаковых
  208.                         }
  209.                     }
  210.                     if(skip){
  211.                         g_1[j].f.pb(k);
  212.  
  213.                     }
  214.                     g_1[k].s.insert(i);
  215.                     g_1[j].s.insert(i); // помечаем что в этих гиперрёбрах содержится вершина i;
  216.                 }
  217.             }
  218.         }
  219.     }
  220.  
  221.     used.resize(m, false);
  222. // Если захочется посмотреть на ребёрный граф:
  223. //    for(auto i : g_1){
  224. //        for(auto j : i.f){
  225. //            cout << j << " ";
  226. //        }
  227. //        cout << "\n";
  228. //    }
  229.  
  230.     loop(i, 0, m){
  231.         if(!used[i]){
  232.             bool ch = dfs(i);
  233.  
  234.             if(!ch){
  235.                 cout << "Not Helly!\n";
  236.                 return;
  237.             }
  238.         }
  239.     }
  240.     cout << "Is Helly\n";
  241. //    cve(g_1);
  242.  
  243. }
  244. void solve(){
  245.     cin >> n >> m;
  246.  
  247.     g.resize(n);
  248.     inc.resize(n);
  249.     loop(i, 0, n){
  250.         loop(j, 0, m){
  251.             int q;
  252.             cin >> q;
  253.             inc[i].pb(q);
  254.             if(q){
  255.                 g[i].pb(j);
  256.             }
  257.         }
  258.     }
  259.     cve(g);
  260. //    s_helly();
  261.  
  262.     // 1)
  263. //    hip_1(1); // сюда вводишь вершину X;
  264.  
  265.     // 2)
  266. //    ve_2(2); // сюда ввести номер гиперребра
  267.  
  268.     // 3)
  269. //    dv_hip_3();
  270.  
  271.     // 4)
  272. //    l4();
  273.     // 5)
  274. //    l5(); // там внутри вводится множество V
  275.  
  276.     // 6)
  277. //    l6(); // там внутри вводится множество E
  278.     // 7) через 3 секунды начнётся мастурбация.
  279.     s_helly();
  280. }
  281.  
  282. int main() {
  283. #ifdef DEBUG
  284.     freopen("text.txt", "r", stdin);
  285.     freopen("output.txt", "w", stdout);
  286. #endif
  287.     solve();
  288. }
  289.  
Advertisement
Add Comment
Please, Sign In to add comment