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 = 2e4 + 5; 
  12.  
  13. int n, m; 
  14. vector<int> adj[N];
  15.  
  16. bool vis[N];
  17. int num_cc; // Số thành phần liên thông 
  18. int cnt[N]; // cnt[i] = Số đỉnh có trong thành phần liên thông thứ i
  19. int root[N]; // root[i] = Nút gốc của cây dfs của thành phần liên thông thứ i
  20.  
  21. void dfs1(int u) {
  22. 	vis[u] = true;  
  23. 	cnt[num_cc]++; 
  24. 	for (int v : adj[u]) {
  25. 		if (!vis[v]) dfs1(v); 
  26. 	}
  27. }
  28.  
  29. // Do ban đầu có thể có nhiều thành phần liên thông nên ta sẽ đi tính đáp án cho từng thành phần liên thông
  30. // f(X) = Số cặp (a, b) sao cho mọi đường đi từ a đến b bắt buộc phải đi qua X
  31. // Cách đếm tương tự với bài WEATHER nhưng phức tạp hơn do khi bỏ một đỉnh thì có thể bị tách ra nhiều thành phần liên thông
  32. // Với mỗi đỉnh v sao cho v là con của X trên cây dfs, nếu low[v] >= tin[X]
  33. // thì sau khi bỏ đỉnh X, cây con gốc v sẽ bị tách ra riêng một thành phần liên thông
  34. // Lưu ý ở phần công thức tính để tránh bị đếm lặp
  35. ll ans;  
  36. int tin[N], low[N], timer;
  37. int sz[N];
  38.  
  39. void dfs2(int i, int u, int p) {
  40. 	tin[u] = low[u] = ++timer; 
  41. 	sz[u] = 1;  
  42. 	int tot = 0;  
  43.  
  44. 	for (int v : adj[u]) {
  45. 		if (v == p) continue; 
  46. 		if (!tin[v]) {
  47. 			dfs2(i, v, u); 
  48. 			low[u] = min(low[u], low[v]); 
  49. 			sz[u] += sz[v];
  50. 			if (low[v] >= tin[u]) {
  51. 				ans += 1ll * sz[v] * (cnt[i] - sz[v] - tot - 1);
  52. 				tot += sz[v];
  53. 			}
  54. 		}
  55. 		else {
  56. 			low[u] = min(low[u], tin[v]);
  57. 		}
  58. 	}
  59. }
  60.  
  61. int main() {
  62. 	ios::sync_with_stdio(false); 
  63. 	cin.tie(nullptr); 	
  64. 	cin >> n >> m; 
  65. 	for (int i = 0; i < m; i++) {
  66. 		int u, v; 
  67. 		cin >> u >> v; 
  68. 		adj[u].push_back(v); 
  69. 		adj[v].push_back(u); 
  70. 	}
  71.  
  72. 	num_cc = 0;  
  73. 	for (int u = 1; u <= n; u++) {
  74. 		if (!vis[u]) {
  75. 			num_cc++; 
  76. 			root[num_cc] = u;  
  77. 			dfs1(u); 
  78. 		}
  79. 	}
  80.  
  81. 	ans = 0;  
  82. 	timer = 0;
  83. 	for (int i = 1; i <= num_cc; i++) {
  84. 		dfs2(i, root[i], -1); 
  85. 	}
  86.  
  87. 	cout << fixed << setprecision(9) << (double)ans / n << '\n';
  88. }
  89.  
Success #stdin #stdout 0s 5288KB
comments (?)
stdin 
5 5
1 2
2 3
3 4
4 5
5 3
stdout 
1.400000000
https://ideone.com/ZYmqmX
language:
C++14 (gcc 8.3)
created:
275 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!