AquaBlitz11

Supernova

Jul 27th, 2020
413
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.48 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5. using pii = pair<int, int>;
  6.  
  7. const int N = 100010;
  8.  
  9. int n;
  10. vector<pii> G[N];
  11. int U[N], V[N], deg[N], sz[N];
  12. ll ans[N];
  13.  
  14. void dfs(int u, int p, int e)
  15. {
  16.     sz[u] = 1;
  17.     for (auto v : G[u]) {
  18.         if (v.first != p && deg[v.first] == 0) {
  19.             dfs(v.first, u, v.second);
  20.             sz[u] += sz[v.first];
  21.         }
  22.     }
  23.     ans[e] = (ll)(n-sz[u]) * sz[u];
  24. }
  25.  
  26. int main()
  27. {
  28.     scanf("%d%*d", &n); // n = m
  29.     for (int i = 1; i <= n; ++i) {
  30.         int u, v;
  31.         scanf("%d%d", &u, &v);
  32.         U[i] = u, V[i] = v;
  33.         G[u].push_back({v, i});
  34.         G[v].push_back({u, i});
  35.         ++deg[u], ++deg[v];
  36.     }
  37.     queue<int> Q;
  38.     for (int u = 1; u <= n; ++u) {
  39.         if (deg[u] == 1)
  40.             Q.push(u);
  41.     }
  42.     while (!Q.empty()) {
  43.         int u = Q.front();
  44.         Q.pop();
  45.         for (auto v : G[u]) {
  46.             if (deg[v.first] > 0) {
  47.                 --deg[u];
  48.                 if (--deg[v.first] == 1)
  49.                     Q.push(v.first);
  50.             }
  51.         }
  52.     }
  53.  
  54.     for (int u = 1; u <= n; ++u) {
  55.         if (deg[u] == 2) // start from node in cycle only
  56.             dfs(u, 0, 0);
  57.     }
  58.     for (int i = 1; i <= n; ++i) {
  59.         if (i != 1)
  60.             printf(" ");
  61.         if (deg[U[i]] == 2 && deg[V[i]] == 2) // ignore edge in cycle
  62.             ans[i] = 0;
  63.         printf("%lld", ans[i]);
  64.     }
  65.     printf("\n");
  66.    
  67.     return 0;
  68. }
Add Comment
Please, Sign In to add comment