fork(1) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Edge { int to, id; };
  5. int N, M, K;
  6. vector<vector<Edge>> g;
  7. vector<int> tin, low, isBridge;
  8. int timerDFS = 0;
  9.  
  10. void dfsBridge(int u, int pEdge) {
  11.     tin[u] = low[u] = ++timerDFS;
  12.     for (auto e : g[u]) {
  13.         if (e.id == pEdge) continue;
  14.         if (!tin[e.to]) {
  15.             dfsBridge(e.to, e.id);
  16.             low[u] = min(low[u], low[e.to]);
  17.             if (low[e.to] > tin[u]) isBridge[e.id] = 1;
  18.         } else low[u] = min(low[u], tin[e.to]);
  19.     }
  20. }
  21.  
  22. vector<int> comp, compSize;
  23. void dfsComp(int u, int c) {
  24.     comp[u] = c; compSize[c]++;
  25.     for (auto e : g[u]) if (comp[e.to] == -1 && !isBridge[e.id]) dfsComp(e.to, c);
  26. }
  27.  
  28. vector<vector<int>> tree;
  29. vector<int> subSize;
  30. vector<bool> removed;
  31. long long badPairs = 0;
  32.  
  33. int getSize(int u, int p) {
  34.     subSize[u] = compSize[u];
  35.     for (int v : tree[u]) if (v != p && !removed[v]) subSize[u] += getSize(v, u);
  36.     return subSize[u];
  37. }
  38.  
  39. int getCentroid(int u, int p, int n) {
  40.     for (int v : tree[u]) if (v != p && !removed[v]) if (subSize[v] > n/2) return getCentroid(v, u, n);
  41.     return u;
  42. }
  43.  
  44. void collect(int u, int p, int d, vector<pair<int,int>>& nodes) {
  45.     nodes.push_back({d, compSize[u]});
  46.     for (int v : tree[u]) if (v != p && !removed[v]) collect(v, u, d+1, nodes);
  47. }
  48.  
  49. void solveCentroid(int c) {
  50.     vector<pair<int,int>> distAll;
  51.     distAll.push_back({0, compSize[c]});
  52.     for (int v : tree[c]) if (!removed[v]) {
  53.         vector<pair<int,int>> distSub;
  54.         collect(v, c, 1, distSub);
  55.         for (auto [da, ca] : distSub)
  56.             for (auto [db, cb] : distAll)
  57.                 if (da + db < K) badPairs += 1LL * ca * cb;
  58.         distAll.insert(distAll.end(), distSub.begin(), distSub.end());
  59.     }
  60. }
  61.  
  62. void decompose(int u) {
  63.     int n = getSize(u, -1);
  64.     int c = getCentroid(u, -1, n);
  65.     solveCentroid(c);
  66.     removed[c] = true;
  67.     for (int v : tree[c]) if (!removed[v]) decompose(v);
  68. }
  69.  
  70. int main() {
  71.     ios::sync_with_stdio(false);
  72.     cin.tie(nullptr);
  73.  
  74.     cin >> N >> M >> K;
  75.     g.assign(N+1, {});
  76.     for (int i=1; i<=M; i++) {
  77.         int u,v; cin >> u >> v;
  78.         g[u].push_back({v,i});
  79.         g[v].push_back({u,i});
  80.     }
  81.  
  82.     tin.assign(N+1,0); low.assign(N+1,0); isBridge.assign(M+1,0);
  83.     for (int i=1; i<=N; i++) if (!tin[i]) dfsBridge(i,-1);
  84.  
  85.     comp.assign(N+1,-1);
  86.     int compCnt=0;
  87.     for (int i=1; i<=N; i++) if (comp[i]==-1) { compSize.push_back(0); dfsComp(i,compCnt++); }
  88.  
  89.     tree.assign(compCnt,{});
  90.     for (int u=1; u<=N; u++) for (auto e:g[u]) if (isBridge[e.id]) {
  91.         int cu=comp[u], cv=comp[e.to];
  92.         if (cu!=cv) tree[cu].push_back(cv);
  93.     }
  94.  
  95.     subSize.assign(compCnt,0);
  96.     removed.assign(compCnt,false);
  97.  
  98.     long long total = accumulate(compSize.begin(),compSize.end(),0LL);
  99.     long long totalPairs = total*(total-1)/2;
  100.     decompose(0);
  101.     cout << totalPairs - badPairs << "\n";
  102. }
  103.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
8 9 2
1 5
1 5
2 3
2 6
3 7
4 8
5 6
6 7
7 8
stdout 
15
https://ideone.com/JTN7Gv
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!