[Light OJ] 1300 - Odd Personality

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 1300 - Odd Personality
Source            : Light Online Judge
Category          : Graph Theory
Algorithm         : Bridge Tree
Verdict           : Accepted
#include <bits/stdc++.h>
 
using namespace std;
 
 
#define WHITE                  1
#define RED                    2
#define BLUE                   3
 
static const int maxn = 1e5 + 5;
 
struct node
{
    int v, e;
    node(int v = 0, int e = 0) : v(v), e(e) {}
};
 
vector <node> graph[maxn];
bool isBridge[maxn], vis[maxn];
int dis[maxn], low[maxn], timer;
 
inline void findBridge(int u, int p)
{
    vis[u] = 1;
    dis[u] = low[u] = timer++;
    vector <node>::iterator E;
    for (E = graph[u].begin(); E != graph[u].end(); E++)
    {
        int v = E->v;
        int e = E->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  node_compo[maxn], edge_compo[maxn], num_node_in_a_compo[maxn], start[maxn];
 
inline void bridgeTree(int src)
{
    int cur_compo = compo;
    used[src] = 1;
    node_compo[src] = cur_compo;
    num_node_in_a_compo[cur_compo]++;
    if (start[cur_compo] == -1) start[cur_compo] = src;
    queue <int> PQ;
    PQ.push(src);
    while (!PQ.empty())
    {
        int u = PQ.front(); PQ.pop();
        vector <node>::iterator E;
        for (E = graph[u].begin(); E != graph[u].end(); E++)
        {
            int v = E->v;
            int e = E->e;
            if (used[v])
            {
                if (isBridge[e] == 0) edge_compo[e] = cur_compo;
                continue;
            }
            if (isBridge[e])
            {
                compo++;
                // make tree
                bridgeTree(v);
            }
            else
            {
                PQ.push(v);
                used[v] = 1;
                node_compo[v] = cur_compo;
                edge_compo[e] = cur_compo;
 
                num_node_in_a_compo[cur_compo]++;
            }
        }
    }
}
 
 
inline int read()           { int a; scanf("%d", &a); return a; }
 
int tNode, tEdge;
int color[maxn];
 
inline bool bicolor(int src, int compo_num)  // if a graph is bipartite graph, the graph must not
{                                            // contain any odd length cycle
    queue <int> PQ;
    PQ.push(src);
    color[src] = RED;
    while (!PQ.empty())
    {
        int u = PQ.front(); PQ.pop();
        vector <node>::iterator E;
        for (E = graph[u].begin(); E != graph[u].end(); E++)
        {
            int v = E->v;
            int e = E->e;
            if (node_compo[v] != compo_num || edge_compo[e] != compo_num) continue;
            if (color[v] == WHITE)
            {
                if (color[u] == RED) color[v] = BLUE;
                else color[v] = RED;
                PQ.push(v);
            }
            else if (color[u] == color[v])
            {
                return true;         // odd length cycle found
            }
        }
    }
    return false;   // Bipartite Graph, even length cycle
}
 
void init()
{
    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;
        node_compo[i] = 0;
        edge_compo[i] = 0;
        start[i] = -1;
        color[i] = WHITE;  // ALL WHITE
        num_node_in_a_compo[i] = 0;
        graph[i].clear();
    }
}
 
int main()
{
    int tc = read();
    for (int tcase = 1; tcase <= tc; tcase++)
    {
        init();
        tNode = read();
        tEdge = read();
        for (int e = 1; e <= tEdge; e++)
        {
            int u = read();
            int v = read();
            graph[u].push_back({v, e});
            graph[v].push_back({u, e});
        }
        for (int i = 0; i < tNode; i++)
        {
            if (!vis[i])
            {
                findBridge(i, -1);
            }
        }
        for (int i = 0; i < tNode; i++)
        {
            if (!used[i])
            {
                bridgeTree(i);
                compo++;
            }
        }
        int total = 0;
        for (int c = 1; c <= compo; c++)
        {
            bool odd;
            if (num_node_in_a_compo[c]) ODD = bicolor(start[c], c);
            if (ODD) total += num_node_in_a_compo[c];
        }
        printf("Case %d: %d\n", tcase, total);
    }
}