fork download
copy 
  1. //#pragma comment(linker, "/stack:200000000")
  2. //#pragma GCC optimize("Ofast")
  3. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  4. //#pragma GCC optimize("unroll-loops")
  5.  
  6. #include <iostream>
  7. #include <stdlib.h>
  8. #include <cmath>
  9. #include <algorithm>
  10. #include <vector>
  11. #include <set>
  12. #include <map>
  13. #include <random>
  14. #include <assert.h>
  15. #include <memory.h>
  16.  
  17. #define uint unsigned int
  18. #define ll long long
  19. #define ull unsigned long long
  20. #define ld long double
  21. #define rep(i, l, r) for (int i = l; i < r; i++)
  22. #define repb(i, r, l) for (int i = r; i > l; i--)
  23. #define sz(a) (int)a.size()
  24. #define fi first
  25. #define se second
  26. #define mp(a, b) make_pair(a, b)
  27.  
  28. using namespace std;
  29.  
  30. inline void setmin(int &x, int y) { if (y < x) x = y; }
  31. inline void setmax(int &x, int y) { if (y > x) x = y; }
  32. inline void setmin(ll &x, ll y) { if (y < x) x = y; }
  33. inline void setmax(ll &x, ll y) { if (y > x) x = y; }
  34.  
  35. const int N = 100000;
  36. const int inf = (int)1e9 + 1;
  37. const ll big = (ll)1e18 + 1;
  38. const int P = 239;
  39. const int P1 = 31;
  40. const int P2 = 57;
  41. const int MOD = (int)1e9 + 7;
  42. const int MOD1 = (int)1e9 + 9;
  43. const int MOD2 = 998244353;
  44. const double eps = 1e-9;
  45. const double pi = atan2(0, -1);
  46. const int ABC = 26;
  47.  
  48. vector<int> g[N];
  49. int cnt[N];
  50. bool used[N];
  51. int ttt = 0;
  52. int in[N];
  53. int up[N];
  54.  
  55. set<pair<int, int> > good;
  56.  
  57. void dfs(int u, int par) {
  58.     used[u] = true;
  59.     in[u] = up[u] = ttt++;
  60.     for (int v : g[u]) {
  61.         if (!used[v]) {
  62.             dfs(v, u);
  63.             setmin(up[u], up[v]);
  64.             if (up[v] == in[v]) {
  65.                 good.insert({u, v});
  66.             }
  67.         } else {
  68.             if (v != par) {
  69.                 setmin(up[u], in[v]);
  70.             }
  71.         }
  72.     }
  73. }
  74.  
  75. int main()
  76. {
  77.     //freopen("a.in", "r", stdin);
  78.     //freopen("dsu.out", "w", stdout);
  79.     ios_base::sync_with_stdio(0);
  80.     cin.tie(0);
  81.     cout.precision(20);
  82.     cout << fixed;
  83.     //ll TL = 0.95 * CLOCKS_PER_SEC;
  84.     //clock_t time = clock();
  85.     int n,m;
  86.     cin >> n >>m;
  87.     int u, v;
  88.     while (cin >> u >> v) {
  89.         u--; v--;
  90.         g[u].push_back(v);
  91.         g[v].push_back(u);
  92.         cnt[u]++; cnt[v]++;
  93.     }
  94.     map<int, int> MMM;
  95.     rep(i, 0, n) {
  96.         MMM[cnt[i]]++;
  97.     }
  98.     map<pair<int, int>, int> mapa;
  99.     rep(i, 0, n) {
  100.         for (int j : g[i]) {
  101.             if (i < j) {
  102.                 int d1 = cnt[i], d2 = cnt[j];
  103.                 if (d1 > d2) {
  104.                     swap(d1, d2);
  105.                 }
  106.                 mapa[{d1, d2}]++;
  107.             }
  108.         }
  109.     }
  110.     map<int, int> mmm[n];
  111.     rep(i, 0, n) {
  112.         for (int j : g[i]) {
  113.             mmm[i][cnt[j]]++;
  114.         }
  115.     }
  116.     dfs(0, -1);
  117.     ll ans = 0;
  118.     rep(i, 0, n) {
  119.         for (int j : g[i]) {
  120.             if (i < j) {
  121.                 if (good.count({i, j}) || good.count({j, i})) {
  122.                     continue;
  123.                 }
  124.                 int d1 = cnt[i], d2 = cnt[j];
  125.                 ll v = 0;
  126.                 if (d1 - 1 == d2 - 1) {
  127.                     v = 1LL * MMM[d1 - 1] * (MMM[d1 - 1] - 1) / 2;
  128.                     v -= mapa[{min(d1 - 1, d2 - 1), max(d1 - 1, d2 - 1)}];
  129.                 } else if (d2 - d1 == 1) {
  130.                     v = 1LL * MMM[d1 - 1] * (MMM[d2 - 1] - 1);
  131.                     v -= mapa[{min(d1 - 1, d2 - 1), max(d1 - 1, d2 - 1)}] - mmm[i][d1 - 1];
  132.                 } else if (d1 - d2 == 1) {
  133.                     v = 1LL * (MMM[d1 - 1] - 1) * MMM[d2 - 1];
  134.                     v -= mapa[{min(d1 - 1, d2 - 1), max(d1 - 1, d2 - 1)}] - mmm[j][d2 - 1];
  135.                 } else {
  136.                     v = 1LL * MMM[d1 - 1] * MMM[d2 - 1];
  137.                     v -= mapa[{min(d1 - 1, d2 - 1), max(d1 - 1, d2 - 1)}];
  138.                 }
  139.                 ans += v;
  140.                 //cout << i << " " << j << " " << " " << v << " " << mapa[{min(d1 - 1, d2 - 1), max(d1 - 1, d2 - 1)}] << endl;
  141.                 //ans += v - mapa[{min(d1 - 1, d2 - 1), max(d1 - 1, d2 - 1)}];
  142.                 if (d2 - d1 == 1) {
  143.                     ans += MMM[d1 - 1] - 1 - mmm[j][d1 - 1];
  144.                 } else {
  145.                     ans += MMM[d1 - 1] - mmm[j][d1 - 1];
  146.                 }
  147.                 if (d1 - d2 == 1) {
  148.                     ans += MMM[d2 - 1] - 1 - mmm[i][d2 - 1];
  149.                 } else {
  150.                     ans += MMM[d2 - 1] - mmm[i][d2 - 1];
  151.                 }
  152.                 //cout << i << " " << j << " " << ans << endl;
  153.                 //ans = 0;
  154.                 //ans += MMM[d2 - 1] - mmm[i][d2 - 1];
  155.                 //ans += MMM[d1 - 1] - mmm[j][d1 - 1];
  156.                 /*MMM[d1]--;
  157.                 MMM[d2]--;
  158.                 MMM[d1 - 1]++;
  159.                 MMM[d2 - 1]++;
  160.                 MMM[d1]++;
  161.                 MMM[d2]++;
  162.                 MMM[d1 - 1]--;
  163.                 MMM[d2 - 1]--;*/
  164.             }
  165.         }
  166.     }
  167.     cout << ans << "\n";
  168.     return 0;
  169. }
Success #stdin #stdout 0s 18856KB
comments ()
stdin
copy 
4 4
1 2
1 3
2 3
1 4
stdout
copy 
4
https://ideone.com/6DW1hn
language:
C++14 (gcc 8.3)
created:
6 years 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!