fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. #ifndef LOCAL
  4. #define endl '\n'
  5. #endif
  6.  
  7. #define fr(i, a, b) for(int i = a; i <= b; i++)
  8. #define rf(i, a, b) for(int i = a; i >= b; i--)
  9. #define pf push_front
  10. #define pb push_back
  11. #define fi first
  12. #define se second
  13. #define all(x) x.begin(), x.end()
  14. #define rall(x) x.rbegin(), x.rend()
  15. #define sz(x) (int)x.size()
  16. #define rsz resize()
  17. #define lb lower_bound
  18. #define ub upper_bound
  19. #define br cout << endl
  20.  
  21. typedef long long ll;
  22. typedef long double f80;
  23. typedef pair<int,int> pii;
  24. typedef pair<ll,ll> pll;
  25.  
  26. int pct(int x) { return __builtin_popcount(x); }
  27. int pct(ll x) { return __builtin_popcountll(x); } 
  28. int bit(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))
  29. int bit(ll x) { return 63 - __builtin_clzll(x); } // floor(log2(x))
  30. int cdiv(int a, int b) { return a / b + !(a < 0 || a % b == 0); }
  31. ll cdiv(ll a, ll b) { return a / b + !(a < 0 || a % b == 0); }
  32. int nxt_C(int x) { int c = x & -x, r = x + c; return (((r ^ x) >> 2) / c) | r; }
  33. ll nxt_C(ll x) { ll c = x & -x, r = x + c; return (((r ^ x) >> 2) / c) | r; }
  34.  
  35. vector<int> get_bits(int mask) {
  36. 	vector<int> bb;
  37. 	while(mask) { int b = bit(mask); bb.pb(b); mask ^= (1 << b); }
  38. 	reverse(all(bb));
  39. 	return bb;
  40. }
  41.  
  42. int get_mask(vector<int> v) {
  43. 	int mask = 0;
  44. 	for(int x : v) { mask ^= (1 << x); }
  45. 	return mask;
  46. }
  47.  
  48. template<typename T>
  49. void uniq(vector<T> &v) { sort(all(v)); v.resize(unique(all(v)) - v.begin()); }
  50. template<typename T>
  51. void leftShift(vector<T> &v, ll k) { k %= sz(v); if(k < 0) k += sz(v); rotate(v.begin(), v.begin() + k, v.end()); }
  52. template<typename T>
  53. void rightShift(vector<T> &v, ll k) { leftShift(v, sz(v) - k); }
  54.  
  55. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  56.  
  57. ll rand(ll l, ll r){
  58. 	uniform_int_distribution<ll> uid(l, r);
  59. 	return uid(rng);
  60. }
  61.  
  62. void pr() {}
  63. void sc() {}
  64.  
  65. template <typename Head, typename... Tail>
  66. void pr(Head H, Tail... T) { cout << H << " "; pr(T...); }
  67.  
  68. template <typename Head, typename... Tail>
  69. void sc(Head &H, Tail &... T) { cin >> H; sc(T...); }
  70.  
  71. #ifdef LOCAL
  72. #define debug(...) cerr << "[L:" << __LINE__ << "][" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  73. #else
  74. #define debug(...) 42
  75. #endif
  76.  
  77. #ifndef LOCAL
  78. string to_string(__int128 x) {
  79. 	string s = "";
  80. 	bool neg = 0;
  81. 	if(x < 0) { s += "-"; neg = 1; x = -x; }
  82. 	if(!x) s += '0';
  83. 	while(x) {
  84. 		int rem = x % 10;
  85. 		s += to_string(rem);
  86. 		x /= 10;
  87. 	}
  88. 	reverse(s.begin() + neg, s.end());
  89. 	return s;
  90. }
  91. #endif
  92.  
  93. const int mod = 1e9 + 7; // 998244353;
  94.  
  95. int pwr(int a,int b) {
  96. 	int ans = 1;
  97. 	while(b) {
  98. 		if(b & 1) ans = (ans * 1LL * a) % mod;
  99. 		a = (a * 1LL * a) % mod;
  100. 		b >>= 1;
  101. 	}
  102. 	return ans;
  103. }
  104.  
  105. /*
  106. 	Lookout for overflows!!
  107. 	Check array sizes!!
  108. 	Clear before test cases!!
  109. 	Use the correct modulo!!
  110. 	Check for corner cases!!
  111. 	Are you forgetting something?!
  112. 	Read problem statement carefully!!!
  113. */
  114.  
  115. const int N = 1e5 + 5;
  116. set<int> g[N];
  117. set<int> vis;
  118. int ans;
  119.  
  120. void dfs(int u) {
  121. 	vis.erase(u);
  122.     for(int x : vis) {
  123. 		if(!g[u].count(x)) {
  124. 			ans--;
  125. 			dfs(x);
  126. 		}
  127. 	}
  128. }
  129.  
  130. void solve() {
  131. 	int n, m;
  132. 	sc(n, m);
  133. 	ans = n - 1;
  134. 	fr(i, 1, n) {
  135. 		vis.insert(i);
  136. 	}
  137. 	fr(i, 1, m) {
  138. 		int u, v;
  139. 		sc(u, v);
  140. 		g[u].insert(v);
  141. 		g[v].insert(u);
  142. 	}
  143. 	while(!vis.empty()) {
  144. 		int u = *vis.begin();
  145. 		dfs(u);
  146. 	}
  147. 	cout << ans;
  148. }
  149.  
  150. signed main() {
  151. 	ios :: sync_with_stdio(0);
  152. 	cin.tie(0);
  153. 	cout.tie(0);
  154. 	int t;
  155. 	// cin >> t;
  156. 	t = 1;
  157. 	for(int tt = 1; tt <= t; tt++) {
  158. 		solve();
  159. 	}
  160. 	return 0;
  161. }
Runtime error #stdin #stdout 0s 7876KB
comments (?)
stdin
copy 
6 11
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
stdout
copy 
Standard output is empty
https://ideone.com/5oF69o
language:
C++14 (gcc 8.3)
created:
4 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!