fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define CLR(x,y) memset(x,y,sizeof(x))
  6. #define SQ(x) ((x)*(x))
  7. #define ALL(x) (x).begin(),(x).end()
  8. #define LL long long
  9.  
  10. const int Size = 1000055;
  11. const LL mod = 1000000007;
  12.  
  13. int N, M, K;
  14. int Time = 0;
  15. vector<int> Graph[Size];
  16. int disc[Size], low[Size];
  17. int ap[Size];
  18. int vis[Size], par[Size];
  19. LL res = 0;
  20. LL SIZE[Size];
  21. int ID[Size];
  22. int color = 1;
  23. int totalAP = 0;
  24.  
  25. void AP(int cur) {
  26.     disc[cur] = low[cur] = ++Time;
  27.     vis[cur] = 1;
  28.     int child = 0;
  29.     vector<int> adj;
  30.  
  31.     for (int i = 0; i < (int) Graph[cur].size(); i++) {
  32.         int v = Graph[cur][i];
  33.  
  34.         LL prvTime = Time;
  35.  
  36.         if (vis[v] == 0) {
  37.             par[v] = cur;
  38.             child++;
  39.             AP(v);
  40.             bool f = false;
  41.             if (par[cur] == -1 && child > 1) {
  42.                 ap[cur] = 1;
  43.                 f = true;
  44.             }
  45.             low[cur] = min(low[v], low[cur]);
  46.             if (par[cur] != -1 && low[v] >= disc[cur]) {
  47.                 ap[cur] = 1;
  48.                 f = true;
  49.             }
  50.             if(f == true){ /// There is a sub component which is connected to the main graph by edge cur-v
  51.                 adj.pb(Time - prvTime);
  52.                 /// Time - prvTime = the size of this sub component
  53.             }
  54.         } else if (v != par[cur]) {
  55.             low[cur] = min(disc[v], low[cur]);
  56.         }
  57.     }
  58.  
  59.     if(ap[cur] == 1) totalAP++;
  60.     if(adj.size() == 0) return;
  61.  
  62.     LL sizeOfOther = 0;
  63.     for(int i = 0;i<adj.size();i++){
  64.         sizeOfOther += adj[i];
  65.     }
  66.  
  67.     LL sizeOfCurSubGraph = SIZE[ID[cur]] - sizeOfOther - 1;
  68.     adj.pb(sizeOfCurSubGraph);
  69.  
  70.     for(int i = 0;i<adj.size();i++){
  71.         LL sz = adj[i];
  72.         /// No of ways to select (P,V) for current articulation point
  73.         LL add = sz * (SIZE[ID[cur]] - sz - 1);
  74.         add %= mod;
  75.         res += add;
  76.         res %= mod;
  77.     }
  78. }
  79.  
  80. void DFS(int cur){
  81.     ID[cur] = color;
  82.     SIZE[color]++; /// Size of the current component
  83.     for(int i = 0;i<Graph[cur].size();i++){
  84.         int v = Graph[cur][i];
  85.         if(ID[v] != -1) continue;
  86.         DFS(v);
  87.     }
  88. }
  89.  
  90. void solve() {
  91.     CLR(SIZE,0);
  92.     CLR(ID,-1);
  93.     /// Update color and size of different component in the graph.
  94.     for(int i = 1;i<=N;i++){
  95.         if(ID[i] != -1) continue;
  96.         DFS(i);
  97.         color++;
  98.     }
  99.     for(int i = 0;i<Size;i++){
  100.         disc[i] = low[i] = ap[i] = vis[i] = 0;
  101.         par[i] = -1;
  102.     }
  103.     for (int i = 1; i <= N; i++) {
  104.         if (vis[i] == 0) {
  105.             AP(i);
  106.         }
  107.     }
  108. }
  109.  
  110. int main () {
  111.  
  112.     int u,v;
  113.     scanf("%d %d %d", &N, &M, &K);
  114.     for (int i = 0; i < M; i++) {
  115.         scanf("%d %d", &u, &v );
  116.         Graph[u].pb(v);
  117.         Graph[v].pb(u);
  118.     }
  119.     solve();
  120.     printf("%lld\n",res);
  121.  
  122.     return 0;
  123. }
  124.  
Success #stdin #stdout 0.01s 46448KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/SGAlwv
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!