deushiro

Untitled

Feb 23rd, 2020
308
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.13 KB | None | 0 0
  1.  
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <set>
  5. #include <stdlib.h>
  6. #include <algorithm>
  7. #include <iostream>
  8. #include <iterator>
  9. #include <vector>
  10. #include <set>
  11. #include <string>
  12. #include <fstream>
  13.  
  14. using namespace std;
  15.  
  16. ifstream in("input.txt");
  17. ofstream out("output.txt");
  18.  
  19. struct node {
  20.     string person;
  21.     set<node*> friends;
  22.     node(string p_) : person(p_) {};
  23.     node(string p_, set<node*> f_) : person(p_), friends(f_) {};
  24.     void print() {
  25.         cout << person << " (" << this << ") knows: { ";
  26.         for (auto f : friends)
  27.             cout << f->person << " ";
  28.         cout << "}\n";
  29.     }
  30. };
  31.  
  32. class graph {
  33. private:
  34.     set<node*> g;
  35. public:
  36.     void addNode(string p_) {
  37.         node* n = new node(p_);
  38.         g.insert(n);
  39.     }
  40.     void addEdge(string p1_, string p2_) {
  41.         node* n1 = NULL, * n2 = NULL;
  42.         for (auto p : g) {
  43.             if (p->person == p1_) { n1 = p; }
  44.             else if (p->person == p2_) { n2 = p; }
  45.         }
  46.         if (n1 && n2)
  47.             n1->friends.insert(n2), n2->friends.insert(n1);
  48.     }
  49.     set<node*> getUniverse() {
  50.         return g;
  51.     }
  52.     void print() {
  53.         for (auto p : g)
  54.             (*p).print();
  55.     }
  56. };
  57.  
  58. vector<string> ans;
  59. int maxi = 0;
  60.  
  61. /*
  62. void set_print(set<node*> s) {
  63.     if (s.size() > maxi) {
  64.         ans.clear();
  65.         for (auto p : s)
  66.             ans.push_back(p->person);
  67.         maxi = s.size();
  68.     }
  69. }
  70. */
  71. void set_print(set<node*> s) {
  72.     out << "[ " << s.size() << " ] \n";
  73. }
  74.  
  75. set<node*> set_union(set<node*> a, set<node*> b) {
  76.     set<node*> c;
  77.     set_union(a.begin(), a.end(), b.begin(), b.end(), inserter(c, c.end()));
  78.     return c;
  79. }
  80.  
  81. set<node*> set_intersection(set<node*> a, set<node*> b) {
  82.     set<node*> c;
  83.     set_intersection(a.begin(), a.end(), b.begin(), b.end(), inserter(c, c.end()));
  84.     return c;
  85. }
  86.  
  87. //note, set_difference is the relative compliment on input set a//
  88. set<node*> set_difference(set<node*> a, set<node*> b) {
  89.     set<node*> c;
  90.     set_difference(a.begin(), a.end(), b.begin(), b.end(), inserter(c, c.end()));
  91.     return c;
  92. }
  93.  
  94. void bronKerbosch(set<node*> R, set<node*> P, set<node*> X) {
  95.     if (P.empty() && X.empty()) {
  96.         out << "Clique found: ";
  97.         set_print(R);
  98.     }
  99.     set<node*>::iterator v = P.begin();
  100.     while (!P.empty() && v != P.end()) {
  101.         set<node*> singleton = { (*v) };
  102.         bronKerbosch(set_union(R, singleton), set_intersection(P, (*v)->friends), set_intersection(X, (*v)->friends));
  103.         P = set_difference(P, singleton);
  104.         X = set_union(X, singleton);
  105.         if (!P.empty())
  106.             v = P.begin();
  107.     }
  108. }
  109.  
  110. int main() {
  111.    
  112.     int tt;
  113.     in >> tt;
  114.     while (tt--) {
  115.         graph g;
  116.         int n, m;
  117.         in >> n >> m;
  118.         for (int i = 0; i < m; ++i) {
  119.             g.addNode(to_string(i + 1));
  120.         }
  121.         vector<vector<int>> z(m);
  122.         for (int i = 0; i < m; ++i) {
  123.             int k;
  124.             in >> k;
  125.             for (int j = 0; j < k; ++j) {
  126.                 int x;
  127.                 in >> x;
  128.                 z[i].push_back(x);
  129.             }
  130.         }
  131.         for (int i = 0; i < m; ++i) {
  132.             for (int j = 0; j < m; ++j) {
  133.                 bool flag = true;
  134.                 if (i != j) {
  135.                     vector<int> c(n + 1, 0);
  136.                     for (int k : z[i]) {
  137.                         c[k]++;
  138.                     }
  139.                     for (int k : z[j]) {
  140.                         c[k]++;
  141.                     }
  142.                     for (int k = 0; k < n + 1; ++k) {
  143.                         if (c[k] > 1)
  144.                             flag = false;
  145.                     }
  146.                     if (flag) {
  147.                         g.addEdge(to_string(i + 1), to_string(j + 1));
  148.                     }
  149.                 }
  150.             }
  151.         }
  152.         set<node*> R, P, X;
  153.         P = g.getUniverse();
  154.         maxi = 0;
  155.         bronKerbosch(R, P, X);/*
  156.         out << ans.size() << endl;
  157.         for (auto t : ans) {
  158.             out << t << " ";
  159.         }
  160.         out << endl;*/
  161.         out << endl << endl;
  162.  
  163.     }
  164.  
  165.     return 0;
  166. }
Advertisement
Add Comment
Please, Sign In to add comment