[Light OJ] 1308 – Ant Network

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 1308 – Ant Network
Source            : Light Online Judge
Category          : Graph Theory
Algorithm         : Block Cut Tree, Articulation Point
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define FI              freopen("in.txt", "r", stdin)
#define FO              freopen("out.txt", "w", stdout)
#define FAST            ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
 
#define FOR(i, n)       for (int i = 1; i <= n; i++)
#define For(i, n)       for (int i = 0; i < n; i++)
#define ROF(i, n)       for (int i = n; i >= 1; i--)
#define Rof(i, n)       for (int i = n-1; i >= 0; i--)
#define FORI(i, n)      for (auto i : n)
#define eb              push_back //emplace_back
#define ll              long long
#define ull             unsigned long long
#define vi              vector <int>
#define vl              vector <ll>
#define All(a)          a.begin(), a.end()
#define endl            '\n'
#define lb              lower_bound
#define mod             1000000007
 
inline int setbit(int mask, int pos)      { return mask |= (1 << pos); }
inline int resetbit(int mask, int pos)    { return mask &= ~(1 << pos); }
inline int togglebit(int mask, int pos)   { return mask ^= (1 << pos); }
inline bool checkbit(int mask, int pos)   { return (bool)(mask & (1 << pos)); }
 
static const int maxn = 1e5 + 5;
static const int logn = 18;
 
vi graph[maxn], blockCutTree[maxn];
stack <int> s;
int tnode, tedge, tot, dfsTime, child, disc[maxn], low[maxn], bcc[maxn];
bool isart[maxn];
vi bccCompo[maxn];
 
inline void addEdge(int u, int v)
{
      blockCutTree[u].eb(v);
      blockCutTree[v].eb(u);
}
 
inline void findBCC(int u, int p = -1)
{
      dfsTime++;
      disc[u] = low[u] = dfsTime;
      s.push(u);
      int child = 0;
      for (int i = 0; i < graph[u].size(); i++)
      {
            int v = graph[u][i];
            if (v == p) continue;
            if (!disc[v])
            {
                  child++;
                  findBCC(v, u);
                  low[u] = min(low[u], low[v]);
                  if (disc[u] <= low[v])
                  {
                        isart[u] = 1;
                        tot++;
                        int h;
                        do {
                              h = s.top(); s.pop();
                              addEdge(h, tot);
                              bcc[h] = tot;
                              bccCompo[tot].eb(h);
                        } while (h != v);
                        bccCompo[tot].eb(u);
                        addEdge(tot, u);
                  }
            }
            else
            {
                  low[u] = min(low[u], disc[v]);
            }
      }
      if (child == 1 && p <= -1) isart[u] = 0;
}
 
inline void solve(int tnode)
{
      For(i, maxn) isart[i] = 0, disc[i] = 0, low[i] = 0;
      dfsTime = 0;
      tot = tnode;
      FOR(i, tnode) if (!disc[i]) findBCC(i);
      ull ans1 = 0, ans2 = 1;
      for (int i = tnode+1; i <= tot; i++)
      {
            int art = 0;
            for (int j = 0; j < bccCompo[i].size(); j++)
            {
                  int v = bccCompo[i][j];
                  if (isart[v]) art++;
            }
            if (art == 1) ans1++, ans2 *= (ll)(bccCompo[i].size() - art);
      }
      if (tot == tnode+1)
      {
            ans1 = 2;
            ans2 = (ll)(tnode*(tnode-1)/2);
      }
      cout << ans1 << " " << ans2 << endl;
}
 
inline void clean()
{
      For(i, maxn)
      {
            graph[i].clear();
            blockCutTree[i].clear();
            bccCompo[i].clear();
      }
      while (!s.empty()) s.pop();
}
 
int main()
{
      int tc;
      cin >> tc;
      FOR(tcase, tc)
      {
            clean();
            cin >> tnode >> tedge;
            FOR(e, tedge)
            {
                  int u, v;
                  cin >> u >> v;
                  u++;
                  v++;
                  graph[u].eb(v);
                  graph[v].eb(u);
            }
            cout << "Case " << tcase << ": ";
            solve(tnode);
      }
}