[UVa Live Archive] 4186 – Lucky cities

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 4186 – Lucky cities
Source            : UVa Live Archive
Category          : Graph Theory
Algorithm         : Block Cut Tree, Bicoloring
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              emplace_back
#define pb              push_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 sz(a)           a.size()
#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 = 2e5 + 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], used[maxn], inoddcycle[maxn];
int vis[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.emplace(u);
      for (int i = 0; i < graph[u].size(); i++)
      {
            int v = graph[u][i];
            if (v == p) continue;
            if (!disc[v])
            {
                  findBCC(v, u);
                  low[u] = min(low[u], low[v]);
                  if (disc[u] <= low[v])
                  {
                        tot++;
                        int h;
                        do {
                              h = s.top(); s.pop();
                              bccCompo[tot].eb(h);
                        } while (h != v);
                        bccCompo[tot].eb(u);
                  }
            }
            else
            {
                  low[u] = min(low[u], disc[v]);
            }
      }
}
 
#define WHITE        0
#define BLUE         1
#define RED          2
 
inline bool bicolor(int src)
{
      queue <int> PQ;
      vector <int> vec;
      PQ.emplace(src);
      vec.eb(src);
      vis[src] = BLUE;
      bool ok = true;
      while (!PQ.empty())
      {
            int u = PQ.front(); PQ.pop();
            for (int v : graph[u])
            {
                  if (!used[v]) continue;
                  if (vis[v] == WHITE)
                  {
                        if (vis[u] == BLUE) vis[v] = RED;
                        else vis[v] = BLUE;
                        PQ.emplace(v);
                        vec.eb(v);
                  }
                  else
                  {
                        if (vis[u] == vis[v])
                        {
                              ok = false;
                              break;
                        }
                  }
            }
      }
      for (int v : vec) vis[v] = WHITE;
      return ok;
}
 
inline int solve(int tnode)
{
      For(i, maxn)
      {
            vis[i] = WHITE;
            used[i] = 0;
            inoddcycle[i] = 0;
            disc[i] = 0;
            low[i] = 0;
      }
      dfsTime = 0;
      tot = tnode;
      FOR(i, tnode) if (!disc[i]) findBCC(i);
      for (int i = tnode+1; i <= tot; i++)
      {
            int root = 0;
            int sze = sz(bccCompo[i]);
            if (sze <= 2) continue;
            for (int v : bccCompo[i]) root = v, used[v] = 1;
            bool odd = bicolor(root);
            for (int v : bccCompo[i])
            {
                  used[v] = 0;
                  if (odd == false) inoddcycle[v] = 1;
            }
      }
      int cnt = 0;
      FOR(i, tnode) cnt += inoddcycle[i];
      return cnt;
}
 
inline void clean()
{
      For(i, maxn)
      {
            graph[i].clear();
            bccCompo[i].clear();
      }
      while (!s.empty()) s.pop();
}
 
int main()
{
//      FI;
 
      int tc;
      scanf("%d", &tc);
      FOR(tcase, tc)
      {
            clean();
            scanf("%d %d", &tnode, &tedge);
            FOR(e, tedge)
            {
                  int u, v;
                  scanf("%d %d", &u, &v);
                  graph[u].eb(v);
                  graph[v].eb(u);
            }
            printf("%d\n", solve(tnode));
      }
}