fork download
copy 
  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. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());   
  12.  
  13. const int p = 1e6 + 3; 
  14. const int N = 1e6 + 5; 
  15.  
  16. int n, m;  
  17. vector<int> adj[N]; 
  18. vector<ii> edges; 
  19.  
  20. ll h_val[N]; 
  21. ll h_xor_adj[N]; 
  22.  
  23. void precompute() {
  24. 	for (int u = 1; u <= n; u++) {
  25. 		h_val[u] = rng();  
  26. 	}
  27.  
  28. 	for (int u = 1; u <= n; u++) {
  29. 		for (int v : adj[u]) {
  30. 			h_xor_adj[u] ^= h_val[v];
  31. 		}
  32. 	}
  33. }
  34.  
  35. map<ll, int> cnt[N]; 
  36.  
  37. int main() {
  38. 	ios::sync_with_stdio(false); 
  39. 	cin.tie(nullptr); 	
  40. 	cin >> n >> m; 
  41. 	for (int i = 1; i <= m; i++) {
  42. 		int u, v; 
  43. 		cin >> u >> v; 
  44. 		adj[u].push_back(v); 
  45. 		adj[v].push_back(u); 		
  46. 		edges.push_back({u, v}); 
  47. 	}
  48.  
  49. 	precompute();  
  50.  
  51. 	ll ans = 0;  
  52. 	// Xét các cặp (u, v) mà u, v không phải là bạn của nhau
  53. 	for (int u = 1; u <= n; u++) {
  54. 		ans += cnt[adj[u].size()][h_xor_adj[u]];  
  55. 		cnt[adj[u].size()][h_xor_adj[u]]++; 
  56. 	}
  57.  
  58. 	// Xét các cặp (u, v) mà u, v là bạn của nhau	
  59. 	for (ii e : edges) {
  60. 		int u = e.first, v = e.second; 
  61. 		if (adj[u].size() != adj[v].size()) continue; 
  62. 		h_xor_adj[u] ^= h_val[v], h_xor_adj[v] ^= h_val[u];  
  63. 		ans += (h_xor_adj[u] == h_xor_adj[v]); 
  64. 		h_xor_adj[u] ^= h_val[v], h_xor_adj[v] ^= h_val[u];  
  65. 	}
  66.  
  67. 	cout << ans << '\n'; 
  68. }
Success #stdin #stdout 0.02s 79296KB
comments (?)
stdin
copy 
3 3
1 2
2 3
1 3
stdout
copy 
3
https://ideone.com/5stJQH
language:
C++14 (gcc 8.3)
created:
333 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!