fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <set>
  6. using namespace std;
  7.  
  8. const int MAXN = 100005;
  9.  
  10. vector<int> graph[MAXN];
  11. bool visited[MAXN];
  12. int discoveryTime[MAXN], low[MAXN];
  13. int timer = 0;
  14. vector<pair<int, int>> bridges;
  15.  
  16. // Hàm DFS tìm cầu
  17. void findBridges(int u, int parent) {
  18.     visited[u] = true;
  19.     discoveryTime[u] = low[u] = ++timer;
  20.  
  21.     for (int v : graph[u]) {
  22.         if (v == parent) continue; // Bỏ qua cạnh quay về cha
  23.         if (!visited[v]) {
  24.             findBridges(v, u);
  25.             low[u] = min(low[u], low[v]);
  26.  
  27.             // Kiểm tra nếu (u, v) là cầu
  28.             if (low[v] > discoveryTime[u]) {
  29.                 bridges.emplace_back(u, v);
  30.             }
  31.         } else {
  32.             low[u] = min(low[u], discoveryTime[v]);
  33.         }
  34.     }
  35. }
  36.  
  37. // Hàm DFS để đếm số đỉnh trong một thành phần liên thông
  38. int countComponentSize(int u, vector<bool>& visited) {
  39.     visited[u] = true;
  40.     int size = 1;
  41.     for (int v : graph[u]) {
  42.         if (!visited[v]) {
  43.             size += countComponentSize(v, visited);
  44.         }
  45.     }
  46.     return size;
  47. }
  48.  
  49. int main() {
  50.     int N, M;
  51.     cin >> N >> M;
  52.  
  53.     // Đọc đồ thị
  54.     vector<pair<int, int>> edges;
  55.     for (int i = 0; i < M; ++i) {
  56.         int u, v;
  57.         cin >> u >> v;
  58.         graph[u].push_back(v);
  59.         graph[v].push_back(u);
  60.         edges.emplace_back(u, v); // Lưu danh sách các cạnh
  61.     }
  62.  
  63.     // Tìm các cầu trong đồ thị
  64.     memset(visited, false, sizeof(visited));
  65.     for (int i = 1; i <= N; ++i) {
  66.         if (!visited[i]) {
  67.             findBridges(i, -1);
  68.         }
  69.     }
  70.  
  71.     // Lưu danh sách các cầu để kiểm tra nhanh
  72.     set<pair<int, int>> bridgeSet;
  73.     for (auto [u, v] : bridges) {
  74.         bridgeSet.insert({u, v});
  75.         bridgeSet.insert({v, u}); // Lưu cả hai chiều để kiểm tra nhanh
  76.     }
  77.  
  78.     // Xử lý từng cạnh
  79.     for (auto [u, v] : edges) {
  80.         // Nếu không phải cầu, in 0
  81.         if (bridgeSet.find({u, v}) == bridgeSet.end()) {
  82.             cout << 0 << endl;
  83.             continue;
  84.         }
  85.  
  86.         // Loại bỏ cầu khỏi đồ thị
  87.         graph[u].erase(remove(graph[u].begin(), graph[u].end(), v), graph[u].end());
  88.         graph[v].erase(remove(graph[v].begin(), graph[v].end(), u), graph[v].end());
  89.  
  90.         // Nếu là cầu, tính số cặp không kết nối
  91.         vector<bool> tempVisited(N + 1, false);
  92.  
  93.         // Đếm số đỉnh trong thành phần chứa u
  94.         int sizeU = countComponentSize(u, tempVisited);
  95.  
  96.         // Thành phần chứa v có kích thước là phần còn lại
  97.         int sizeV = N - sizeU;
  98.  
  99.         // Tính số cặp không kết nối
  100.         cout << sizeU * sizeV << endl;
  101.  
  102.         // Khôi phục cầu vào đồ thị
  103.         graph[u].push_back(v);
  104.         graph[v].push_back(u);
  105.     }
  106.  
  107.     return 0;
  108. }
  109.  
Success #stdin #stdout 0.01s 5976KB
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/G3htmU
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!