fork(1) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <string>
  4. #include <vector>
  5. #include <bitset>
  6. #include <stdio.h>
  7. #include <math.h>
  8. using namespace std;
  9. typedef std::vector<int> vi;
  10. typedef std::vector<pair<int, int> > vii;
  11. //----------Main source code -----------------//
  12. bitset<101> colored;
  13. vector<vi> adj;
  14. char color[101];
  15. int n, ans;
  16. vi ansL;
  17. void rcr_bkt(int i){
  18. 	//-----ending the recursion----//
  19. 	if(i==n){
  20. 		int b=0;
  21. 		for(int c=0;c<n;c++)
  22. 			if(color[c]=='b') b++;
  23. 		if(b>ans){
  24. 			ans=b;
  25. 			ansL.clear();
  26. 			for(int c=0;c<n;c++)
  27. 			if(color[c]=='b') ansL.push_back(c);
  28. 		}
  29. 		return;
  30. 	}
  31. 	//-----------------------------//
  32.  
  33. 	//check if it can be colored black
  34. 	bool black = true;
  35. 	for(vi::iterator it=adj[i].begin();it!=adj[i].end();it++)
  36. 		if(colored[*it]&&color[*it]=='b'){
  37. 			black = false;
  38. 			break;
  39. 		}
  40.  
  41. 	//color one by one
  42. 	colored.set(i);
  43. 	if(black){
  44. 		//color node black
  45. 		color[i]='b';
  46. 		rcr_bkt(i+1);
  47. 	}
  48. 	//white
  49. 	color[i]='w';
  50. 	rcr_bkt(i+1);
  51.  
  52. 	colored.reset(i); //reset colored to retain previous state
  53.  
  54. }
  55. int main() {
  56. 	int t, k, a, b;
  57. 	cin >> t;
  58. 	while(t--){
  59. 		cin>>n>>k;
  60. 		adj.assign(n, vi());
  61. 		colored.reset();
  62. 		ans=-1;
  63. 		while(k--){
  64. 			cin >> a>> b;
  65. 			adj[--a].push_back(--b);
  66. 			adj[b].push_back(a);
  67. 		}
  68. 		std::fill_n(color, 101, 'b');
  69. 		rcr_bkt(0);
  70. 		cout<<ans<<endl;
  71. 		for(vi::iterator i=ansL.begin();i!=ansL.end()-1;i++)
  72. 			cout<<*i+1<<" ";
  73. 		if(ans>0)cout<<*(ansL.end()-1)+1;
  74. 		cout<<endl;
  75. 	}
  76. 	return 0;
  77. }
Success #stdin #stdout 0s 3436KB
comments (?)
stdin
copy 
1
6 8
1 2
1 3
2 4
2 5
3 4
3 6
4 6
5 6
stdout
copy 
3
1 4 5
https://ideone.com/AtWxS9
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

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!