fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <fstream>
  3. #include <iostream>
  4. #define sz (int) 1e5 + 5
  5. #define ull unsigned long long
  6. #define ll long long
  7. //#define int long long
  8.  
  9. using namespace std;
  10.  
  11. vector<int> bestblack,curblack;
  12. int colored[105];
  13. vector<int> arr[105];
  14. int freq[3];
  15. int n,k;
  16. bool canbeblack(int i) {
  17.     for(int j = 0; j < arr[i].size(); j++) {
  18.         if(colored[arr[i][j]]) return 0;
  19.     }
  20.     return 1;
  21. }
  22.  
  23. void solve(int i) {
  24.     if(i == n) {
  25.         return;
  26.     }
  27.     if(n - i + curblack.size() < bestblack.size()) {
  28.         return;
  29.     }
  30.  
  31.     if(canbeblack(i)) {
  32.         colored[i] = 1;
  33.         curblack.push_back(i);
  34.         if(curblack.size() >= bestblack.size()) {
  35.             bestblack = curblack;
  36.         }
  37.  
  38.         solve(i+1);
  39.  
  40.         colored[i] = 0;
  41.         curblack.pop_back();
  42.     }
  43.  
  44.     solve(i+1);
  45.  
  46.     //for(int j = 0; j < arr[i].size(); j++) {
  47.     //    solve(arr[i][j]);
  48.     //}
  49. }
  50.  
  51. int32_t main()
  52. {
  53.     ios::sync_with_stdio(0);
  54.     cin.tie(NULL);
  55.     cout.tie(NULL);
  56.  
  57.     //ofstream myfile;
  58.     //myfile.open("output.txt");
  59.  
  60.     int t;cin>>t;
  61.  
  62.     while(t--) {
  63.         curblack.clear();
  64.         bestblack.clear();
  65.         for(int i = 0; i < 101; i++) {
  66.             colored[i] = 0;
  67.             arr[i].clear();
  68.         }
  69.         cin>>n>>k;
  70.         for(int i = 0; i < k; i++) {
  71.             int a,b;cin>>a>>b;a--;b--;
  72.             arr[a].push_back(b);
  73.             arr[b].push_back(a);
  74.         }
  75.         solve(0);
  76.  
  77.         cout << bestblack.size() << '\n';
  78.  
  79.         bool first = 1;
  80.         for(int i = 0; i < bestblack.size(); i++) {
  81.             if(!first) cout << ' ';
  82.             cout << bestblack[i]+1;
  83.             first = 0;
  84.         }
  85.  
  86.         //if(t)
  87.             cout << '\n';
  88.     }
  89.  
  90.     return 0;
  91. }
  92.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OOQhg3
language:
C++ (gcc 8.3)
created:
3 days 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!