fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define ll long long
  4. using namespace std;
  5.  
  6. const int maxn = 2e5 + 7;
  7.  
  8. int num[maxn] , low[maxn] , par[maxn] , sz[maxn] , root[maxn] , timedfs = 0 , id;
  9. vector <int> g[maxn] , bridchild;
  10.  
  11. int n , m;
  12.  
  13. void dfs(int u)
  14. {
  15.     sz[u] = 1;
  16.     low[u] = num[u] = ++timedfs;
  17.     root[u] = id;
  18.  
  19.     for(int v: g[u])
  20.     {
  21.         if(v == par[u]) continue;
  22.  
  23.         if(num[v] == 0)
  24.         {
  25.             par[v] = u;
  26.             dfs(v);
  27.             sz[u] += sz[v];
  28.  
  29.             if(low[v] > num[u]) bridchild.push_back(v);
  30.  
  31.             low[u] = min(low[u] , low[v]);
  32.         }
  33.         else low[u] = min(low[u] , num[v]);
  34.     }
  35. }
  36.  
  37. void solve()
  38. {
  39.     cin >> n >> m;
  40.     for(int i = 1; i <= m; i++)
  41.     {
  42.         int u , v; cin >> u >> v;
  43.         g[u].push_back(v);
  44.         g[v].push_back(u);
  45.     }
  46.  
  47.     int tplt = 0;
  48.  
  49.     vector <int> sztplt;
  50.  
  51.     for(int i = 1; i <= n; i++)
  52.     {
  53.         if(num[i] == 0)
  54.         {
  55.             id = i;
  56.             tplt++;
  57.             dfs(i);
  58.             sztplt.push_back(sz[i]);
  59.         }
  60.     }
  61.  
  62.     if(tplt > 2)
  63.     {
  64.         cout << 0 << '\n'; return;
  65.     }
  66.  
  67.     if(tplt == 2)
  68.     {
  69.         cout << 1LL*(m - bridchild.size())*(sztplt[0] * sztplt[1]) << '\n';
  70.         return;
  71.     }
  72.  
  73.     ll ans = 1LL*(m - bridchild.size())*(n*(n-1)/2 - m);
  74.  
  75.  
  76.     for(int v: bridchild)
  77.     {
  78.         ans += 1LL*sz[v] * (n - sz[v]) - 1;
  79.     }
  80.  
  81.     cout << ans << '\n';
  82.  
  83. }
  84.  
  85.  
  86. signed main()
  87. {
  88.     ios_base::sync_with_stdio(false);
  89.     cin.tie(0); cout.tie(0);
  90.     solve();
  91.     return 0;
  92. }
  93.  
Success #stdin #stdout 0.01s 8436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/c4m6bJ
language:
C++14 (gcc 8.3)
created:
44 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!