fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <cstring>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. int N, M;
  9. vector<vector<int>> graph;
  10. vector<bool> visited;
  11.  
  12. // Hàm DFS để đếm số đỉnh trong thành phần liên thông
  13. int dfs(int u) {
  14.     visited[u] = true;
  15.     int size = 1; // Đếm đỉnh hiện tại
  16.     for (int v : graph[u]) {
  17.         if (!visited[v]) {
  18.             size += dfs(v);
  19.         }
  20.     }
  21.     return size;
  22. }
  23.  
  24. int countDisconnectedPairs(int u, int v) {
  25.     // Tạm thời loại bỏ cạnh (u, v)
  26.     vector<int> temp_u = graph[u];
  27.     vector<int> temp_v = graph[v];
  28.  
  29.     graph[u].erase(remove(graph[u].begin(), graph[u].end(), v), graph[u].end());
  30.     graph[v].erase(remove(graph[v].begin(), graph[v].end(), u), graph[v].end());
  31.  
  32.     // Tìm các thành phần liên thông
  33.     visited.assign(N + 1, false);
  34.     vector<int> componentSizes;
  35.  
  36.     for (int i = 1; i <= N; ++i) {
  37.         if (!visited[i]) {
  38.             componentSizes.push_back(dfs(i));
  39.         }
  40.     }
  41.  
  42.     // Khôi phục cạnh (u, v)
  43.     graph[u] = temp_u;
  44.     graph[v] = temp_v;
  45.  
  46.     // Tính số cặp không thể đi đến nhau
  47.     long long totalPairs = 0;
  48.     for (int size : componentSizes) {
  49.         totalPairs += 1LL * size * (N - size);
  50.     }
  51.  
  52.     return totalPairs / 2; // Vì mỗi cặp được đếm 2 lần
  53. }
  54.  
  55. int main() {
  56.     cin >> N >> M;
  57.  
  58.     graph.assign(N + 1, vector<int>());
  59.     vector<pair<int, int>> edges;
  60.  
  61.     for (int i = 0; i < M; ++i) {
  62.         int u, v;
  63.         cin >> u >> v;
  64.         graph[u].push_back(v);
  65.         graph[v].push_back(u);
  66.         edges.emplace_back(u, v);
  67.     }
  68.  
  69.     for (auto [u, v] : edges) {
  70.         cout << countDisconnectedPairs(u, v) << endl;
  71.     }
  72.  
  73.     return 0;
  74. }
  75.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
5 5
1 2
2 3
3 4
3 5
5 1
stdout
copy 
0
0
4
0
0
https://ideone.com/wTC2e0
language:
C++14 (gcc 8.3)
created:
8 days 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!