HackerEarth Pink and Blue problem solution

In this HackerEarth Pink and Blue problem solution Xenny was a teacher and he had N students. The N children were sitting in a room. Each child was wearing a white T-shirt, with a unique number from the range 1 to N written on it. T-Shirts of pink and blue color were to be distributed among the students by Xenny. This made the students very happy.

Xenny felt that a random distribution of T-Shirts would be very uninteresting. So, he decided to keep an interesting condition:

Every student would get a T-Shirt that is of a different color than his/her friends. That is, if X and Y are friends and X has a Pink T-Shirt, then Y should compulsorily have a Blue T-Shirt, and vice-versa.

Also, Xenny had a belief that Boys should wear blue T-Shirts and Girls should wear pink T-Shirts. If a boy was given a pink T-Shirt or a girl was given a Blue T-Shirt, he called it an inversion.

So, Xenny wanted to distribute T-Shirts in the above-mentioned interesting manner and also wanted to minimize "inversions". Help him solve the task.

Note: There are no disjoint groups of friends in the room. That is, 2 distinct groups with finite number of students do not exist, but exactly 1 group of students exists in the given situation.

HackerEarth Pink and Blue problem solution.

#include <iostream>
#include <vector>
#include <string.h>
#define ll long long
#define pb push_back
using namespace std;

vector<int> g[100007];
char gender[100007];
char color[100007];
int visited[100007];

int vert;
bool ok;
void dfs(int node, char cur_color)
{
  if(visited[node]) return;
  color[node] = cur_color;
  visited[node] = 1;
  
  for(int i=0;i<g[node].size();i++)
  {
    vert = g[node][i];
    if(vert == node) continue;
    if(visited[vert])
    {
      if(cur_color == color[vert])
      {
        ok=false;
        return;
      }
    }
    else
    {
      char new_color;
      if(cur_color == 'P') new_color = 'B';
      else if(cur_color == 'B') new_color = 'P';
      
      color[vert] = new_color;
      dfs(vert, new_color);
    }
  }
}

int main()
{
  memset(gender,0,sizeof(gender));
  memset(color,0,sizeof(color));
  memset(visited,0,sizeof(visited));
  ios_base::sync_with_stdio(false);
  int n,m;
  cin>>n>>m;
  
  for(int i=1;i<=n;i++) cin>>gender[i];
  
  int u,v;
  for(int i=0;i<m;i++)
  {
    cin>>u>>v;
    g[u].pb(v);
    g[v].pb(u);
  }
  
  int ans=0;
  ok=true;
  dfs(1,'P');
  
  if(ok)
  {
    for(int i=1;i<=n;i++)
    {
      if(gender[i] == 'B' && color[i] == 'P') ans++;
      else if(gender[i] == 'G' && color[i] == 'B') ans++;
    }
    
    int tmp=0;
    memset(visited,0,sizeof(visited));
    memset(color,0,sizeof(color));
    
    dfs(1,'B');
    for(int i=1;i<=n;i++)
    {
      if(gender[i] == 'B' && color[i] == 'P') tmp++;
      else if(gender[i] == 'G' && color[i] == 'B') tmp++;
    }
  
    cout << "1p = " << ans << ", 1b = " << tmp << "\n";
  
    ans = min(ans,tmp);
  
    cout << ans << "\n";
  }
  else
  {
    cout << "Not possible\n";
  }
}