fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void solve() {
  5. 	int n, m;
  6. 	cin >> n >> m;
  7. 	int edges[n];
  8. 	memset(edges, 0, sizeof edges);
  9.  
  10. 	for(int i=0;i<n;i++) {
  11. 		edges[i] |= (1 << i);
  12. 	}
  13. 	for(int i=0;i<m;i++) {
  14. 		int u, v;
  15. 		cin >> u >> v;
  16. 		u-=1, v-=1;
  17. 		edges[u] |= (1 << v);
  18. 		edges[v] |= (1 << u);
  19. 	}
  20. 	int mn = n;
  21. 	for(int bitmask = 1; bitmask < (1 << n) ; bitmask++) {
  22. 		int temp = 0;
  23. 		int cnt = 0;
  24. 		for(int i=0; i<n; i++) {
  25. 			if(bitmask & (1 << i) ) {
  26. 				temp |= edges[i];
  27. 				cnt++;
  28. 			}
  29. 		}
  30. 		if( (temp+1) == (1 << n) ) {
  31. 			mn = min(mn, cnt);
  32. 		} 
  33. 	}
  34. 	cout << mn << "\n";
  35. }
  36.  
  37. int main() {
  38. 	int t;
  39. 	cin >> t;
  40. 	while(t--) solve();
  41. }
Runtime error #stdin #stdout 0s 3456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GiDtEj
language:
C++ (gcc 8.3)
created:
7 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!