Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ctime>
- using namespace std;
- #define pb push_back
- #define f first
- #define s second
- #define mp make_pair
- #define ll long long
- #define MAXN 200005
- #define INF 1000000009
- #define MOD 1000000007
- list < set < int > > kerbosh(vector < vector <bool> > a,int SIZE){
- set <int> M,G,K,P;
- list<set<int> > REZULT;
- for (int i=0; i<SIZE;i++)
- {
- K.insert(i);
- }
- int v,Count=0,cnt=0;
- int Stack1[100];
- std::set<int> Stack2[100];
- std::set<int>::iterator theIterator;
- theIterator=K.begin();
- auto t = clock();
- auto pre = t;
- while ((K.size()!=0)||(M.size()!=0))
- {
- if(clock() - t > 10000000){
- cerr << (clock() - t) / 1000000 << " " << (clock() - pre) / 1000000 << " " << v << endl;
- t = clock();
- if(clock() - pre > 1000000 * 20)
- return REZULT;
- }
- if (K.size()!=0)
- {
- theIterator=K.begin();
- v=*theIterator;
- Stack2[++Count]=M;
- Stack2[++Count]=K;
- Stack2[++Count]=P;
- Stack1[++cnt]=v;
- M.insert(v);
- for (int i=0;i<SIZE;i++)
- {
- if (a[v][i])
- {
- theIterator=K.find(i);
- if (theIterator!=K.end())
- {
- K.erase(theIterator);
- }
- theIterator=P.find(i);
- if (theIterator!=P.end())
- {
- P.erase(theIterator);
- }
- }
- }
- theIterator=K.find(v);
- if (theIterator!=K.end())
- {
- K.erase(theIterator);
- }
- }
- else
- {
- if (P.size()==0)
- {
- REZULT.push_back(M);
- }
- v=Stack1[cnt--];
- P=Stack2[Count--];
- K=Stack2[Count--];
- M=Stack2[Count--];
- theIterator=K.find(v);
- if (theIterator!=K.end())
- {
- K.erase(theIterator);
- }
- P.insert(v);
- }
- }
- return REZULT;
- }
- void solve(){
- vector < vector <int> > gr;
- int n, m; // число аудиторий, число мероприятий
- cin >> n >> m;
- vector <vector <int>> v;
- v.resize(m);
- for(int i = 0; i < m; i++){
- int c;
- cin >> c;
- for(int j = 0; j < c; j++){
- int a;
- cin >> a;
- v[i].pb(a);
- }
- }
- gr.clear();
- gr.resize(m+1);
- for(int i = 0; i < m; i++){
- cerr << i << " ";
- for(int j = i+1; j < m; j++){
- set <int> a;
- for(auto x: v[i])
- a.insert(x);
- bool y = 1;
- for(auto x: v[j])
- if(a.find(x) != a.end())
- y = 0;
- if(y){
- gr[i+1].pb(j+1);
- gr[j+1].pb(i+1);
- }
- }
- }
- cerr << endl << gr.size() << " gr:\n";
- for(int i = 0; i < gr.size(); i++){
- cerr << i << ": ";
- for(auto x: gr[i])
- cerr << x << " ";
- cerr << endl;
- }
- cerr << endl;
- vector < vector < bool > > g;
- g.resize(gr.size());
- for(int i = 0; i < gr.size(); i++){
- g[i].resize(gr.size(), 1);
- cerr << i << ": ";
- for(auto x: gr[i]){
- g[i][x] = 0;
- cerr << x << " ";
- }
- cerr << endl;
- }
- cerr << "matrix: \n";
- for(int i = 0; i < gr.size(); i++){
- for(int j = 0; j < gr.size(); j++)
- cerr << g[i][j] << " ";
- cerr << endl;
- }
- cerr << endl;
- auto ans = kerbosh(g, (int)g.size());
- cerr << "ans: \n";
- vector < set <int> > mx;
- set <int> j;
- mx.pb(j);
- while(!ans.empty()){
- auto out = *(ans.rbegin());
- ans.pop_back();
- cerr << out.size() << ": ";
- for(auto x: out)
- cerr << x << " ";
- if(out.size() >= mx[0].size()){
- if(out.size() > mx[0].size()) mx.clear();
- mx.pb(out);
- }
- cerr << endl;
- }
- cerr << endl;
- cerr << "MX.SIZE = " << mx.size() << endl;
- int mx_a = 0;
- set <int> out;
- for(auto x: mx){
- int a = 0;
- for(auto s: x){
- a+= v[s-1].size();
- }
- if(a > mx_a){
- mx_a = a;
- out = x;
- }
- }
- cout << out.size() << endl;
- for(auto x: out)
- cout << x << " ";
- cout << endl;
- }
- int main(){
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int tests = 1;
- #ifdef LOCAL
- bool a;
- a = freopen("in.data", "r", stdin);
- a = freopen("out.data", "w", stdout);
- cin >> tests;
- #endif
- for(int i = 1; i <= tests; i++){
- cerr << "TEST " << i << endl;
- solve();
- }
- cerr << "End of program";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement