Advertisement
MinhNGUYEN2k4

blo

Mar 30th, 2021
186
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.01 KB | None | 0 0
  1. //Nguyen Huu Hoang Minh
  2. #include <bits/stdc++.h>
  3. #define sz(x) int(x.size())
  4. #define all(x) x.begin(),x.end()
  5. #define reset(x) memset(x, 0,sizeof(x))
  6. #define pb push_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define N 100005
  11. #define remain(x) if (x > MOD) x -= MOD
  12. #define ii pair<int, int>
  13. #define iiii pair< ii , ii >
  14. #define viiii vector< iiii >
  15. #define vi vector<int>
  16. #define vii vector< ii >
  17. #define bit(x, i) (((x) >> (i)) & 1)
  18. #define Task "blo"
  19. #define int long long
  20.  
  21. using namespace std;
  22.  
  23. typedef long double ld;
  24. const int inf = 1e10;
  25. const int minf = -1e10;
  26.  
  27. int n, m;
  28. vector<int> a[N];
  29. int num[N], low[N], cnt, par[N];
  30. int child[N];
  31. int cnode[N];
  32.  
  33. void readfile()
  34. {
  35.     ios_base::sync_with_stdio(false);
  36.     cin.tie(0);cout.tie(0);
  37.     if (fopen(Task".inp","r"))
  38.     {
  39.         freopen(Task".inp","r",stdin);
  40.         freopen(Task".out","w",stdout);
  41.     }
  42.     cin >> n >> m;
  43.     for(int i=1; i<=m; i++)
  44.     {
  45.         int u, v;
  46.         cin >> u >> v;
  47.         a[u].pb(v);
  48.         a[v].pb(u);
  49.     }
  50. }
  51.  
  52. void dfs(int u)
  53. {
  54.     int x = (par[u]!=-1)?1:0;
  55.     int sum = 0;
  56.     child[u] = 1;
  57.     num[u] = low[u] = ++cnt;
  58.     for(auto v : a[u])
  59.     {
  60.         if (v==par[u]) continue;
  61.         if (par[v]) low[u] = min(low[u],num[v]);
  62.         else{
  63.             par[v] = u;
  64.             dfs(v);
  65.             child[u] += child[v];
  66.             low[u] = min(low[u],low[v]);
  67.             if (low[v] >= num[u]){
  68.                 x++;
  69.                 cnode[u] += child[v]*(child[v]-1);
  70.                 sum += child[v];
  71.             }
  72.         }
  73.     }
  74.     if (x>=2){
  75.         cnode[u] += (n-sum-1)*(n-sum-2);
  76.         cnode[u] = n*(n-1)-cnode[u];
  77.     }
  78.     else cnode[u] = (n-1)*2;
  79. }
  80.  
  81. void proc()
  82. {
  83.     for(int i=1; i<=n; i++)
  84.     {
  85.         if (!num[i])
  86.         {
  87.             par[i] = -1;
  88.             dfs(i);
  89.         }
  90.     }
  91.     for(int i=1; i<=n; i++)
  92.     {
  93.         cout << cnode[i] << '\n';
  94.     }
  95. }
  96.  
  97. signed main()
  98. {
  99.     readfile();
  100.     proc();
  101.     return 0;
  102. }
  103.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement