fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct comp
  5. {
  6.     bool operator()(const pair<int, int>& a, const pair<int, int>& b)
  7.     {
  8.         return a.second >= b.second;
  9.     }
  10. };
  11.  
  12. int main()
  13. {
  14.     int n,m;
  15.     scanf("%d %d", &n, &m);
  16.     bitset<300> subsets[m];
  17.     bitset<300> nflag[n]; // flag of connected number for each n
  18.     map<int, int> ncount; // count number connected to n
  19.     set<pair<int,int>, comp> setsize_pair;
  20.  
  21.     int size, key;
  22.     for(int i = 0; i < m; i++)
  23.     {
  24.         scanf("%d", &size);
  25.         set<int> tlist;
  26.         for(int p = 0; p < size; p++)
  27.         {
  28.             scanf("%d", &key);
  29.             subsets[i][key] = 1;
  30.             tlist.insert(key);
  31.         }
  32.         setsize_pair.insert(make_pair(i, subsets[i].count()));
  33.         for(int p = 0; p < tlist.size(); p++)
  34.         {
  35.             int ip = *next(tlist.begin(), p);
  36.             for(int i = p; i < tlist.size(); i++)
  37.             {
  38.                 nflag[ip][*next(tlist.begin(), i)] = 1;
  39.                 nflag[*next(tlist.begin(), i)][ip] = 1;
  40.             }
  41.             ncount[ip] = nflag[ip].count();
  42.         }
  43.     }
  44.  
  45.     set<pair<int,int>, comp> ncountset;
  46.     for(auto i : ncount)
  47.     {
  48.         ncountset.insert(i); 
  49.     }
  50.  
  51.     bitset<300> res;
  52.     bitset<300> sel_node;
  53.     set<int> resi;
  54.     for(auto i : ncountset)
  55.     {
  56.         if(res.count() >= n) break;
  57.         if(res != (res | nflag[i.first]))
  58.         {
  59.             res |= nflag[i.first];
  60.             sel_node[i.first] = 1;
  61.         }
  62.     }
  63.     if(!(res.count() >= n))
  64.     {
  65.         printf("-1\n");
  66.         return 0;
  67.     }
  68.     bitset<300> uniquen;
  69.     bitset<300> temp;
  70.     bitset<300> intersection;
  71.     vector<int> choosen_s;
  72.     intersection.set();
  73.     for(auto i : setsize_pair)
  74.     {
  75.         if(temp.count() >= n) break;
  76.         if((subsets[i.first] & sel_node).any() && (temp != (temp | subsets[i.first])))
  77.         {
  78.             uniquen ^= subsets[i.first];
  79.             temp |= subsets[i.first];
  80.             intersection &= subsets[i.first];
  81.             choosen_s.push_back(i.first);
  82.         }
  83.     }
  84.  
  85.     uniquen ^= intersection;
  86.  
  87.     set<int> ans;
  88.     set<int> tans;
  89.     int sans = 300;
  90.     for(auto i = choosen_s.begin(); i != choosen_s.end(); i++)
  91.     {
  92.         temp.reset();
  93.         tans.clear();
  94.         vector<int>::iterator j = choosen_s.begin() + distance(choosen_s.begin(), i);
  95.         for(; j != choosen_s.end(); j++)
  96.         {
  97.             if(temp.count() >= n) break;
  98.             if((subsets[*j] & uniquen).any())
  99.             {
  100.                 temp |= subsets[*j];
  101.                 tans.insert(*j);
  102.             }
  103.         }
  104.         if(temp.count() < n) break;
  105.         if(tans.size() <= sans)
  106.         {
  107.             sans = tans.size();
  108.             ans = tans;
  109.         }
  110.     }
  111.  
  112.     printf("%d\n", ans.size());
  113.     for(auto i = ans.begin(); i != ans.end(); i++)
  114.     {
  115.         if(i == ans.begin()) printf("%d", *i);
  116.         else printf(" %d", *i);
  117.     }
  118. }
Success #stdin #stdout 0s 4384KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/fdPDNq
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!