[Spoj] ONBRIDGE - Online Bridge Searching

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : ONBRIDGE - Online Bridge Searching
Source            : Spoj
Category          : Graph Theory
Algorithm         : Online Bridge Searching
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
inline int read()          { int a; scanf("%d", &a); return a; }
 
static const int maxn = 5e4 + 5;
 
int n,           // number of nodes
    bridge,      // total bridge after each addition of edge
    m,           // number of edge
    bcc[maxn],   // bcc number of i'th node
    comp[maxn],  // connected component no of i'th node
    link[maxn],  // link of parent node
    sz[maxn];    // size of connected component where i'th node associated
 
void init()
{
    for(int i = 0; i < maxn; i++)
    {
       bcc[i] = comp[i] = i;  // BCC and CC of a node, Initially all are isolate.
       link[i] = -1;          // Link of the parent in CC
       sz[i] = 1;             // Size of a CC
    }
    bridge = 0;
}
 
// Output the BCC of a node
int getBCC(int a)
{
    if (a == -1) return -1;
    if (bcc[a] == a) return a;
    else return bcc[a] = getBCC(bcc[a]);
}
 
// Output the root of the component where a is.
int getCOMP(int a)
{
    if (comp[a] == a) return a;
    else return comp[a] = getCOMP(comp[a]);
}
 
// Merging two path, a->LCA, b->LCA
int cs = 0, vis[maxn];
void mergePath(int a, int b)
{
    cs++;
    a = getBCC(a);
    b = getBCC(b);
    vector <int> va, vb;
    int lca = -1;
    while(1)
    {
        if (a != -1)
        {
            a = getBCC(a);
            va.emplace_back(a);
            if (vis[a] == cs)
            {
                lca = a;
                break;
            }
            vis[a] = cs;
            a = link[a];
        }
        if (b != -1)
        {
            b = getBCC(b);
            vb.emplace_back(b);
            if (vis[b] == cs)
            {
                lca = b;
                break;
            }
            vis[b] = cs;
            b = link[b];
        }
    }
    for (int it : va)
    {
        bcc[it] = lca;    // compressing in same BCC
        if (it == lca) break;
        bridge--;
    }
    for (int it : vb)
    {
        bcc[it] = lca;   // compressing in same BCC
        if (it == lca) break;
        bridge--;
    }
}
 
// This reverses the edge of A to root of the connected component
void makeRoot(int a)
{
    int root = a, child = -1;
    while (a != -1)
    {
        int p = getBCC(link[a]);
        link[a] = child;
        comp[a] = root;
        child = a;
        a = p;
    }
    sz[root] = sz[child];
}
 
void addEdge(int a, int b)
{
    a = getBCC(a);
    b = getBCC(b);
    if (a == b) return;  // Case 1
    int u = getCOMP(a);
    int v = getCOMP(b);
    if (u != v)          // Case 2
    {
        bridge++;
        if (sz[u] > sz[v])
        {
            swap(a, b);
            swap(u, v);
        }
        makeRoot(a);
        link[a] = comp[a] = b;
        sz[v] += sz[a];
    }
    else mergePath(a, b);  // Case 3
}
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    int tc = read();
    for (int tcase = 1; tcase <= tc; tcase++)
    {
        init();
        n = read();
        m = read();
        for (int e = 1; e <= m; e++)
        {
            int u = read(), v = read();
            addEdge(u, v);
            printf("%d\n", bridge);
        }
    }
}