[Light OJ] 1291 - Real Life Traffic

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 1291 - Real Life Traffic
Source            : Light Online Judge
Category          : Graph Theory
Algorithm         : Bridge Tree
Verdict           : Accepted

#include <bits/stdc++.h>
 
using namespace std;
 
static const int MAXN = 20000 + 5;
 
struct NODE
{
    int v, e;
    NODE(int v = 0, int e = 0) : v(v), e(e) {}
};
 
vector <NODE> G[MAXN];
vector <int>  TREE[MAXN];

int tNode, tEdge;
bool isBridge[MAXN], vis[MAXN];
int dis[MAXN], low[MAXN], timer;
 
void FIND_BRIDGE(int u = 0, int p = -1)
{
    vis[u] = 1;
    dis[u] = low[u] = timer++;
    vector <NODE>::iterator ele;
    for (ele = G[u].begin(); ele != G[u].end(); ele++)
    {
        int v = ele->v;
        int e = ele->e;
        if (v == p) continue;
        if (!vis[v])
        {
            FIND_BRIDGE(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;
int DEGREE[MAXN];
queue <int> PQ[MAXN];
 
void BRIDGE_TREE(int src = 0)
{
    int cur_compo = compo;
    vis[src] = 1;
    PQ[cur_compo].push(src);   // we can use 1D queue also
    while (!PQ[cur_compo].empty())
    {
        int u = PQ[cur_compo].front(); PQ[cur_compo].pop();
        vector <NODE>::iterator ele;
        for (ele = G[u].begin(); ele != G[u].end(); ele++)
        {
            int v = ele->v;
            int e = ele->e;
            if (vis[v]) continue;
            if (isBridge[e])
            {
                compo++;
 
                //TREE[cur_compo].push_back(compo);
                //TREE[compo].push_back(cur_compo);
 
                DEGREE[cur_compo]++;
                DEGREE[compo]++;
                BRIDGE_TREE(v);
            }
            else
            {
                PQ[cur_compo].push(v);
                vis[v] = 1;
            }
        }
    }
}
 
int INITIALIZE()
{
    timer = 1;
    compo = 1;
    for (int i = 0; i < MAXN; i++)
    {
        isBridge[i] = 0;
        dis[i]      = 0;
        low[i]      = 0;
        G[i].clear();
        TREE[i].clear();
        DEGREE[i] = 0;
    }
}
 
void INITIALIZE2()
{
    for (int i = 0; i < MAXN; i++) vis[i] = 0;
}
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    int tc;
    scanf("%d", &tc);
    for (int tcase = 1; tcase <= tc; tcase++)
    {
        INITIALIZE();
        INITIALIZE2(); 
        scanf("%d %d", &tNode, &tEdge);
        for (int e = 1; e <= tEdge; e++)
        {
            int u, v;
            scanf("%d %d", &u, &v);
            G[u].push_back({v, e});
            G[v].push_back({u, e});
        }
        FIND_BRIDGE(); 
        INITIALIZE2();
        BRIDGE_TREE();
        int leaf = 0;
        for (int i = 1; i <= compo; i++)
        {
            if (DEGREE[i] == 1)    // Leaf node in Bridge Tree
            {
                leaf++;
            }
        }
        int minimum_edge = max((leaf + 1) >> 1, 0);
        printf("Case %d: %d\n", tcase, minimum_edge);
    }
}