fork(1) download
copy 
  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;
  23. vector<int> compSize;
  24. void dfsComp(int u,int c){
  25.     comp[u]=c; compSize[c]++;
  26.     for(auto e:g[u]) if(comp[e.to]==-1 && !isBridge[e.id]) dfsComp(e.to,c);
  27. }
  28.  
  29. vector<vector<int>> tree;
  30. long long badPairs=0;
  31.  
  32. vector<long long> dfsDP(int u,int p){
  33.     vector<long long> cnt(1, compSize[u]); // cnt[0] = size của BCC u
  34.     for(int v:tree[u]) if(v!=p){
  35.         auto child = dfsDP(v,u);
  36.         // đếm cặp giữa child và cnt
  37.         for(int dx=0; dx<(int)child.size(); dx++){
  38.             for(int dy=0; dy<(int)cnt.size(); dy++){
  39.                 if(dx+dy+1 < K){
  40.                     badPairs += child[dx] * cnt[dy];
  41.                 }
  42.             }
  43.         }
  44.         // merge nhỏ vào lớn
  45.         if(child.size() > cnt.size()) swap(child,cnt);
  46.         for(int dx=0; dx<(int)child.size(); dx++){
  47.             cnt[dx+1] += child[dx];
  48.         }
  49.     }
  50.     return cnt;
  51. }
  52.  
  53. int main(){
  54.     ios::sync_with_stdio(false);
  55.     cin.tie(nullptr);
  56.  
  57.     cin>>N>>M>>K;
  58.     g.assign(N+1,{});
  59.     for(int i=1;i<=M;i++){
  60.         int u,v; cin>>u>>v;
  61.         g[u].push_back({v,i});
  62.         g[v].push_back({u,i});
  63.     }
  64.  
  65.     tin.assign(N+1,0); low.assign(N+1,0); isBridge.assign(M+1,0);
  66.     for(int i=1;i<=N;i++) if(!tin[i]) dfsBridge(i,-1);
  67.  
  68.     comp.assign(N+1,-1);
  69.     int compCnt=0;
  70.     for(int i=1;i<=N;i++) if(comp[i]==-1){ compSize.push_back(0); dfsComp(i,compCnt++); }
  71.  
  72.     tree.assign(compCnt,{});
  73.     for(int u=1;u<=N;u++) for(auto e:g[u]) if(isBridge[e.id]){
  74.         int cu=comp[u], cv=comp[e.to];
  75.         if(cu!=cv) tree[cu].push_back(cv);
  76.     }
  77.  
  78.     long long total=accumulate(compSize.begin(),compSize.end(),0LL);
  79.     long long totalPairs=total*(total-1)/2;
  80.  
  81.     dfsDP(0,-1);
  82.  
  83.     cout<<totalPairs-badPairs<<"\n";
  84. }
  85.  
Success #stdin #stdout 0.01s 5292KB
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 
15
https://ideone.com/GOrgqx
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!