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. int main(){
  30.     ios::sync_with_stdio(false);
  31.     cin.tie(nullptr);
  32.     cin>>N>>M>>K;
  33.     g.assign(N+1,{});
  34.     for(int i=1;i<=M;i++){
  35.         int u,v; cin>>u>>v;
  36.         g[u].push_back({v,i});
  37.         g[v].push_back({u,i});
  38.     }
  39.     tin.assign(N+1,0); low.assign(N+1,0); isBridge.assign(M+1,0);
  40.     for(int i=1;i<=N;i++) if(!tin[i]) dfsBridge(i,-1);
  41.  
  42.     comp.assign(N+1,-1);
  43.     int compCnt=0;
  44.     for(int i=1;i<=N;i++) if(comp[i]==-1){ compSize.push_back(0); dfsComp(i,compCnt++); }
  45.  
  46.     vector<vector<int>> tree(compCnt);
  47.     for(int u=1;u<=N;u++){
  48.         for(auto e:g[u]) if(isBridge[e.id]){
  49.             int cu=comp[u], cv=comp[e.to];
  50.             if(cu!=cv) tree[cu].push_back(cv);
  51.         }
  52.     }
  53.  
  54.     long long ans=0;
  55.     for(int i=0;i<compCnt;i++){
  56.         vector<int> dist(compCnt,-1);
  57.         queue<int>q;
  58.         dist[i]=0; q.push(i);
  59.         while(!q.empty()){
  60.             int u=q.front(); q.pop();
  61.             for(int v:tree[u]) if(dist[v]==-1){
  62.                 dist[v]=dist[u]+1; q.push(v);
  63.             }
  64.         }
  65.         for(int j=i+1;j<compCnt;j++){
  66.             if(dist[j]>=K) ans += 1LL*compSize[i]*compSize[j];
  67.         }
  68.     }
  69.     cout<<ans<<"\n";
  70. }
  71.  
Success #stdin #stdout 0s 5324KB
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 
8
https://ideone.com/MrE5s4
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!