fork download 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 1e5 + 5; 
  12.  
  13. int n, m; 
  14.  
  15. int p[N], sz[N]; 
  16.  
  17. void initSet() {
  18. 	for (int u = 1; u <= n; u++) {
  19. 		p[u] = u;   
  20. 		sz[u] = 1; 
  21. 	}
  22. }
  23.  
  24. int findSet(int u) {
  25. 	if (p[u] == u) return u; 
  26. 	return p[u] = findSet(p[u]); 
  27. }
  28.  
  29. void unionSet(int u, int v) {
  30. 	u = findSet(u), v = findSet(v);  
  31. 	if (u == v) return;  
  32. 	if (sz[u] < sz[v]) swap(u, v);  
  33. 	p[v] = u;  
  34. 	sz[u] += sz[v]; 
  35. }
  36.  
  37. bitset<N> dp;    
  38.  
  39. int main() {
  40. 	ios::sync_with_stdio(false); 
  41. 	cin.tie(nullptr); 	
  42. 	cin >> n >> m; 
  43.  
  44. 	initSet();   
  45.  
  46. 	for (int i = 0; i < m; i++) {
  47. 		int a, b; 
  48. 		cin >> a >> b; 
  49. 		unionSet(a, b); 
  50. 	}
  51.  
  52. 	dp[0] = 1;   
  53.  
  54. 	for (int u = 1; u <= n; u++) {
  55. 		if (u == findSet(u)) {
  56. 			dp |= (dp << sz[u]); 
  57. 		}
  58. 	} 
  59.  
  60. 	for (int i = 1; i <= n; i++) cout << dp[i]; 
  61. }
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin 
5 3
1 2
2 3
1 5
stdout 
10011
https://ideone.com/9GuMrO
language:
C++14 (gcc 8.3)
created:
331 days 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!