[toph.co] Kingdom - Great Roads of Destiny

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Kingdom - Great Roads of Destiny
Source            : toph.co
Category          : Graph Theory
Algorithm         : Bridge Tree, Tree Diameter
Verdict           : Accepted 
 
#include <bits/stdc++.h>
 
using namespace std;
 
 
inline int read()     { int a; scanf("%d", &a); return a; }
 
 
static const int maxn = 2 * 1e5 + 5;
static const int logn = 20;
 
 
struct node
{
    int v, e;
    node(int v = 0, int e = 0) : v(v), e(e) {}
};
 
vector <node> G[maxn];
 
bool isBridge[maxn], vis[maxn];
int timer, dis[maxn], low[maxn];
 
inline void findBridge(int u, int p = -1)
{
    vis[u] = 1;
    dis[u] = low[u] = timer++;
    for (node g : G[u])
    {
        int v = g.v;
        int e = g.e;
        if (v == p) continue;
        if (!vis[v])
        {
            findBridge(v, u);
            low[u] = min(low[u], low[v]);
            if (dis[u] < low[v])
            {
                isBridge[e] = 1;
            }
        }
        else
        {
            low[u] = min(low[u], dis[v]);
        }
    }
}
 
int compo;
bool used[maxn];
int compo_num[maxn];
 
vector <int> TREE[maxn];
 
inline void bridgeTree(int src)
{
    used[src] = 1;
    int cur_compo = compo;
    compo_num[src] = cur_compo;
    queue <int> PQ;
    PQ.push(src);
    while (!PQ.empty())
    {
        int u = PQ.front(); PQ.pop();
        for (node g : G[u])
        {
            int v = g.v;
            int e = g.e;
            if (used[v]) continue;
            if (isBridge[e])
            {
                compo++;
 
                TREE[cur_compo].push_back(compo);
                TREE[compo].push_back(cur_compo);
 
                bridgeTree(v);
            }
            else
            {
                PQ.push(v);
 
                used[v] = 1;
                compo_num[v] = cur_compo;
            }
        }
    }
}
 
int father[maxn][logn];
int depth[maxn];
 
inline void dfs(int u, int p = -1)
{
    for (int i = 1; i < logn; i++)
        father[u][i] = father[father[u][i-1]][i-1];
    for (int v : TREE[u])
    {
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        father[v][0] = u;
        dfs(v, u);
    }
}
 
inline int findLCA(int u, int v)
{
    if (depth[u] < depth[v]) swap(u, v);
 
    for (int i = logn - 1; i >= 0; i--)
    {
        if (depth[father[u][i]] >= depth[v])
        {
            u = father[u][i];
        }
    }
    if (u == v) return u;
    for (int i = logn- 1; i >= 0; i--)
    {
        if (father[u][i] != father[v][i])
        {
            u = father[u][i];
            v = father[v][i];
        }
    }
    return father[u][0];
}
 
 
int distance(int u, int v)
{
    int lca = findLCA(u, v);
    int d = depth[u] + depth[v] - 2 * depth[lca];
    return d;
}
 
void INITIALIZE()
{
    timer = 1;
    compo = 1;
    for (int i = 0; i < maxn; i++)
    {
        dis[i] = 0;
        low[i] = 0;
        isBridge[i] = 0;
        vis[i] = 0;
        used[i] = 0;
        depth[i] = 0;
        compo_num[i] = -1;
        G[i].clear();
        TREE[i].clear();
    }
}
 
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    int tc = read();
    for (int tcase = 1; tcase <= tc; tcase++)
    {
        INITIALIZE();
        int tNode = read();
        int tEdge = read();
        int root = tNode;
        for (int e = 1; e <= tEdge; e++)
        {
            int u = read();
            int v = read();
            G[u].push_back({v, e});
            G[v].push_back({u, e});
            root = min(root, min(u, v));
        }
        findBridge(root);
        bridgeTree(root);
        depth[1] = 1;  // first coomponet is 1
        dfs(1);
        int tQuery = read();
        printf("Case %d:\n", tcase);
        for (int q = 1; q <= tQuery; q++)
        {
            int u = read();
            int v = read();
            int cu = compo_num[u];  // which component has the node u
            int cv = compo_num[v];  // which component has the node v
            int num_greatRoad = 0;
            assert(cu != -1 && cv != -1);
            if (cu != cv) num_greatRoad = distance(cu, cv);
            printf("%d\n", num_greatRoad);
        }
    }
}