fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Edge { int to, id; };
  5.  
  6. int N, M, K;
  7. vector<vector<Edge>> g;
  8. vector<int> tin, low, isBridge;
  9. int timerDFS = 0;
  10.  
  11.  
  12. void dfsBridge(int u, int pEdge) {
  13.     tin[u] = low[u] = ++timerDFS;
  14.     for (auto e : g[u]) {
  15.         int v = e.to, id = e.id;
  16.         if (id == pEdge) continue;
  17.         if (!tin[v]) {
  18.             dfsBridge(v, id);
  19.             low[u] = min(low[u], low[v]);
  20.             if (low[v] > tin[u]) {
  21.                 isBridge[id] = 1;
  22.             }
  23.         } else {
  24.             low[u] = min(low[u], tin[v]);
  25.         }
  26.     }
  27. }
  28.  
  29.  
  30. vector<int> comp;
  31. vector<int> compSize;
  32. void dfsComp(int u, int c) {
  33.     comp[u] = c;
  34.     compSize[c]++;
  35.     for (auto e : g[u]) {
  36.         if (comp[e.to] == -1 && !isBridge[e.id]) {
  37.             dfsComp(e.to, c);
  38.         }
  39.     }
  40. }
  41.  
  42.  
  43. vector<vector<int>> tree;
  44. vector<int> subSize;
  45. vector<bool> removed;
  46.  
  47. int getSize(int u, int p) {
  48.     subSize[u] = compSize[u];
  49.     for (int v : tree[u]) if (v != p && !removed[v]) {
  50.         subSize[u] += getSize(v, u);
  51.     }
  52.     return subSize[u];
  53. }
  54.  
  55. int getCentroid(int u, int p, int n) {
  56.     for (int v : tree[u]) if (v != p && !removed[v]) {
  57.         if (subSize[v] > n/2) return getCentroid(v, u, n);
  58.     }
  59.     return u;
  60. }
  61.  
  62. long long badPairs = 0;
  63.  
  64. void collect(int u, int p, int d, vector<pair<int,int>>& nodes) {
  65.     nodes.push_back({d, compSize[u]});
  66.     for (int v : tree[u]) if (v != p && !removed[v]) {
  67.         collect(v, u, d+1, nodes);
  68.     }
  69. }
  70.  
  71. void solveCentroid(int c) {
  72.     vector<pair<int,int>> distAll;
  73.     distAll.push_back({0, compSize[c]});
  74.  
  75.     for (int v : tree[c]) if (!removed[v]) {
  76.         vector<pair<int,int>> distSub;
  77.         collect(v, c, 1, distSub);
  78.  
  79.  
  80.         for (auto [da, ca] : distSub) {
  81.             for (auto [db, cb] : distAll) {
  82.                 if (da + db < K) badPairs += 1LL * ca * cb;
  83.             }
  84.         }
  85.         // merge vào distAll
  86.         distAll.insert(distAll.end(), distSub.begin(), distSub.end());
  87.     }
  88. }
  89.  
  90. void decompose(int u) {
  91.     int n = getSize(u, -1);
  92.     int c = getCentroid(u, -1, n);
  93.     solveCentroid(c);
  94.     removed[c] = true;
  95.     for (int v : tree[c]) if (!removed[v]) {
  96.         decompose(v);
  97.     }
  98. }
  99.  
  100. int main() {
  101.     ios::sync_with_stdio(false);
  102.     cin.tie(nullptr);
  103.  
  104.     cin >> N >> M >> K;
  105.     g.assign(N+1, {});
  106.     for (int i=1; i<=M; i++) {
  107.         int u, v;
  108.         cin >> u >> v;
  109.         g[u].push_back({v, i});
  110.         g[v].push_back({u, i});
  111.     }
  112.  
  113.     tin.assign(N+1, 0);
  114.     low.assign(N+1, 0);
  115.     isBridge.assign(M+1, 0);
  116.  
  117.     for (int i=1; i<=N; i++) if (!tin[i]) dfsBridge(i, -1);
  118.  
  119.     comp.assign(N+1, -1);
  120.     int compCnt = 0;
  121.     for (int i=1; i<=N; i++) {
  122.         if (comp[i] == -1) {
  123.             compSize.push_back(0);
  124.             dfsComp(i, compCnt);
  125.             compCnt++;
  126.         }
  127.     }
  128.  
  129.     tree.assign(compCnt, {});
  130.     for (int u=1; u<=N; u++) {
  131.         for (auto e : g[u]) {
  132.             if (isBridge[e.id]) {
  133.                 int cu = comp[u];
  134.                 int cv = comp[e.to];
  135.                 if (cu != cv) {
  136.                     tree[cu].push_back(cv);
  137.                 }
  138.             }
  139.         }
  140.     }
  141.  
  142.     subSize.assign(compCnt, 0);
  143.     removed.assign(compCnt, false);
  144.  
  145.     long long total = accumulate(compSize.begin(), compSize.end(), 0LL);
  146.     long long totalPairs = total * (total - 1);
  147.  
  148.     decompose(0);
  149.  
  150.     cout << totalPairs - badPairs << "\n";
  151. }
  152.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
8 9 2
1 5
1 5
2 3
2 6
3 7
4 8
5 6
6 7
7 8
stdout
copy 
43
https://ideone.com/l1oa12
language:
C++14 (clang 8.0)
created:
11 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!