Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bits/stdc++.h"
- //speed coding
- #define mp make_pair
- #define cve(tpy) for (auto i : tpy) {for(auto j : i){cout << j << " "; }cout << "\n";} ;
- #define f first
- #define s second
- #define loop(i, x, n) for (int i = x; i < n; i++)
- #define joop(x, n) for (ll j = x; j < n; j++)
- #define lp(n) for (ll i = 0; i < n; i++)
- #define err cout << "ERROR" << endl;
- #define all(x) x.begin(), x.end()
- #define pb push_back
- #define sz(x) x.size()
- #define rndm rng()
- // types
- #define pii pair<int, int>
- #define pll pair<ll, ll>
- #define vvi vector<vector<int>>
- #define vvll vector<vector<ll>>
- typedef long long ll;
- typedef long double ld;
- // types of data
- #define inf 1000000000
- #define infll 1000000000000000000
- #define INF ll(1e18)
- #define md 998244353
- #define mod 1000000009
- //#define K 239017
- #define DEBUG 1
- using namespace std;
- mt19937_64 rng(113113);
- uniform_int_distribution<ll> drist;
- vector<vector<int>> g, inc;
- int n, m;
- void hip_1(int x){
- cout << "1) \n";
- for(auto i : g[x-1]){
- cout << i + 1 << "\n"; // гиперребра дл вершины x
- }
- }
- void ve_2(int u){
- cout << "2)\n";
- loop(i, 0, n){
- for(auto v : g[i]){
- if(u == v+1){
- cout << i+1 << '\n';
- continue;
- }
- }
- }
- }
- void dv_hip_3(){
- cout << "3)\n";
- vector<vector<int>> g1;
- g1.resize(m);
- loop(i, 0, n){
- loop(j, 0, m){
- if(inc[i][j]){
- g1[j].pb(i);
- }
- }
- }
- cve(g1); // выводим наш двойственный гиперграф
- }
- void l4(){
- // ребёрный
- cout << "4)\nedge graph: \n";
- vector<vector<int>> g_1;
- g_1.resize(m);
- loop(i, 0, n){
- for(auto j : g[i]){
- for(auto k : g[i]){
- if(k != j){
- int skip = 1;
- for(auto kinj : g_1[j]){
- if(kinj == k){
- skip = 0;
- break; // защита от одинаковых
- }
- }
- if(skip){
- g_1[j].pb(k);
- }
- }
- }
- }
- }
- cve(g_1);
- // вершинный
- cout << "vertex graph: \n";
- vector<vector<int>> g_2;
- g_2.resize(n);
- loop(i, 0, n){
- loop(j, 0, n){
- if(j != i){
- for(auto q : g[i]){
- for(auto q_1 : g[j]){
- if(q_1 == q){
- g_2[i].pb(j); // вершинный гиперграф, получается из того, что две гипервершины имеют один гиперграф.
- }
- }
- }
- }
- }
- }
- cve(g_2);
- }
- void l5(){
- cout << "5)\n";
- vector<vector<int>> g_1;
- g_1.resize(n);
- vector<int> v;
- int v_n;
- cin >> v_n;
- v.resize(v_n);
- loop(i, 0, v_n) cin >> v[i];
- loop(i, 0, n){
- for(auto q : v){
- if(q - 1 == i){
- g_1[i] = g[i];
- }
- }
- }
- cve(g_1);
- }
- void l6(){
- cout << "6)\n";
- vector<vector<int>> g_1;
- vector<int> e;
- int e_n;
- cin >> e_n;
- e.resize(e_n);
- g_1.resize(n);
- loop(i, 0, e_n) cin >> e[i];
- loop(i, 0, n){
- int added = 0;
- for(auto ej : g[i]){ // перебираю гиперрёбра вершины
- for(auto k : e){
- if(k-1 == ej){
- g_1[i] = g[i];
- added = 1;
- break;
- }
- }
- if(added) break;
- }
- }
- cve(g_1);
- }
- vector<pair<vector<int>, set<int>>> g_1;
- vector<bool> used;
- bool dfs(int v){
- used[v] = true;
- for(int u : g_1[v].f){
- if(!used[u]){
- dfs(u);
- std::vector<int> common_data;
- 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));
- // err
- // for(auto qq : common_data){
- // cout << qq << " ";
- // }
- // cout << common_data[0] << '\n';
- if(!common_data.empty()){ // если пересечение не пустое, то всё круто
- return true;
- }
- return false;
- }
- }
- return true;
- }
- void s_helly(){
- // ребёрный
- cout << "7) HELLY CONDITION \n";
- g_1.resize(m);
- loop(i, 0, n){
- for(auto j : g[i]){
- for(auto k : g[i]){
- if(k != j){
- int skip = 1;
- for(auto kinj : g_1[j].f){
- if(kinj == k){
- skip = 0;
- break; // защита от одинаковых
- }
- }
- if(skip){
- g_1[j].f.pb(k);
- }
- g_1[k].s.insert(i);
- g_1[j].s.insert(i); // помечаем что в этих гиперрёбрах содержится вершина i;
- }
- }
- }
- }
- used.resize(m, false);
- // Если захочется посмотреть на ребёрный граф:
- // for(auto i : g_1){
- // for(auto j : i.f){
- // cout << j << " ";
- // }
- // cout << "\n";
- // }
- loop(i, 0, m){
- if(!used[i]){
- bool ch = dfs(i);
- if(!ch){
- cout << "Not Helly!\n";
- return;
- }
- }
- }
- cout << "Is Helly\n";
- // cve(g_1);
- }
- void solve(){
- cin >> n >> m;
- g.resize(n);
- inc.resize(n);
- loop(i, 0, n){
- loop(j, 0, m){
- int q;
- cin >> q;
- inc[i].pb(q);
- if(q){
- g[i].pb(j);
- }
- }
- }
- cve(g);
- // s_helly();
- // 1)
- // hip_1(1); // сюда вводишь вершину X;
- // 2)
- // ve_2(2); // сюда ввести номер гиперребра
- // 3)
- // dv_hip_3();
- // 4)
- // l4();
- // 5)
- // l5(); // там внутри вводится множество V
- // 6)
- // l6(); // там внутри вводится множество E
- // 7) через 3 секунды начнётся мастурбация.
- s_helly();
- }
- int main() {
- #ifdef DEBUG
- freopen("text.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment