[toph.co] The Spy Cats

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : The Spy Cats
Source            : toph.co
Category          : Graph Theory
Algorithm         : Block Cut Tree, Articulation Point
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll                             long long
#define vi                             vector <int>
#define eb                             emplace_back
#define em                             emplace
#define sz(a)                          (int)a.size()
 
static const int maxn = 3e5 + 5;
 
vi graph[maxn], tree[maxn];
stack <int> s;
int tnode, tedge, tot, dfsTime, child, disc[maxn],
    low[maxn], bcc[maxn];
bool isart[maxn];
 
int total_node_in_this_region[maxn], which_region[maxn];
 
inline void findBCC(int u, int p, int region)
{
      total_node_in_this_region[region]++;
      which_region[u] = region;
      dfsTime++;
      disc[u] = low[u] = dfsTime;
      s.em(u);
      int child = 0;
      for (int v : graph[u])
      {
            if (v == p) continue;
            if (!disc[v])
            {
                  child++;
                  findBCC(v, u, region);
                  low[u] = min(low[u], low[v]);
                  if (disc[u] <= low[v])
                  {
                        isart[u] = 1;
                        tot++;
                        int h;
                        do {
                              h = s.top(); s.pop();
                              tree[h].eb(tot);
                              tree[tot].eb(h);
                        } while (h != v);
                        tree[u].eb(tot);
                        tree[tot].eb(u);
                  }
            }
            else
            {
                  low[u] = min(low[u], disc[v]);
            }
      }
      if (child == 1 && p <= -1) isart[u] = 0;
}
 
int subtree_size[maxn];
int father[maxn];
bool vis[maxn];
 
inline void dfs(int u, int p = -1)
{
      vis[u] = 1;
      father[u] = p;
      subtree_size[u] = 0;
      if (u <= tnode) subtree_size[u] = 1;
      for (int v : tree[u])
      {
            if (v == p) continue;
            dfs(v, u);
            subtree_size[u] += subtree_size[v];
      }
}
 
inline ll get(int u) // for u node only
{
      ll tnodes = total_node_in_this_region[ which_region[u] ];
      if (tnodes == 1) return 0;
      if (tnodes == 2) return 1;
      if (!isart[u]) return tnodes - 1;
      vector <ll> data;
      for (int v : tree[u])
      {
            if (v == father[u])
            {
                  ll sze = tnodes - subtree_size[u];
                  data.eb(sze);
            }
            else
            {
                  ll sze = subtree_size[v];
                  data.eb(sze);
            }
      }
      ll sum = 0;
      ll ans = 0;
      for (ll d : data)
      {
            ans += sum * d;
            sum += d;
      }
      ans += tnodes - 1;
      return ans;
}
 
inline void clean()
{
      dfsTime = 0;
      tot = 0;
      for (int i = 0; i < maxn; i++)
      {
            graph[i].clear();
            tree[i].clear();
            disc[i] = 0;
            low[i] = 0;
            isart[i] = 0;
            total_node_in_this_region[i] = 0;
            which_region[i] = 0;
            subtree_size[i] = 0;
            vis[i] = 0;
            father[i] = 0;
      }
}
 
int main()
{
//      freopen("in.txt", "r", stdin);
 
      int tc;
      scanf("%d", &tc);
      for (int tcase = 1; tcase <= tc; tcase++)
      {
            clean();
            scanf("%d %d", &tnode, &tedge);
            for (int e = 1; e <= tedge; e++)
            {
                  int u, v;
                  scanf("%d %d", &u, &v);
                  graph[u].eb(v);
                  graph[v].eb(u);
            }
            int region = 0;
            tot = tnode;
            for (int i = 1; i <= tnode; i++)
            {
                  if (disc[i] == 0)
                  {
                        dfsTime = 0;
                        region++;
                        findBCC(i, -1, region);
                  }
            }
            for (int i = 1; i <= tnode; i++)
            {
                  if (vis[i] == 0)
                  {
                        dfs(i);
                  }
            }
            printf("Case %d:\n", tcase);
            for (int i = 1; i <= tnode; i++) printf("%lld\n", get(i));
      }
}