Analysis: Decorating The Pastures by Kalki Seksaria

This is a variant of the problem of determining if a graph is 2-colorable. We can start by considering the case where all the pastures are connected. For now, we can ignore the costs of the signs, and simply determine if we can place the signs such that two pastures are decorated with different letters if they are connected by a path. Without loss of generality, we can start by guessing that the first pasture will have an 'F'. Now, all of our decisions as to whether to place an 'F' or a 'J' at any other vertex are forced. We can DFS, and place an 'F' on every vertex that has a neighboring pasture with a 'J', and vice-versa. If this procedure is successful, we have found a valid assignment of the signs. Now, the only decision we made was to decide whether pasture 1 would have an 'F' or a 'J'. If the number of 'J' signs in this assignment is at least as large as the number of 'F' signs, then we are good. If not, we can simply reverse all of the 'F' and 'J' signs. This gives us the maximum number of 'J' signs. If this assignment procedure is unsuccessful, and results in one pasture needing both an 'F' sign and a 'J' sign, then a valid assignment cannot be found and we should output -1. We can now generalize this to graphs where not all of the pastures are connected by solving each connected component separately. If even one connected component is unsuccessful, then we should output -1. If the assignment for all the connected components is successful, then the maximum number of 'J' signs is just the sum of this quantity for all the connected components.

Here is Mark's code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cassert>

using namespace std;

#define MAXN 50010

int color[MAXN];
int colorcount[2];
vector<int> E[MAXN];

bool dfs(int u, int c) {
  if(color[u] != -1) return color[u] == c;
  color[u] = c;
  colorcount[c]++;

  for(int i = 0; i < E[u].size(); i++) {
    if(!dfs(E[u][i], 1 - c)) {
      return false;
    }
  }
  return true;
}

int main() {
  freopen("decorate.in", "r", stdin);
  freopen("decorate.out", "w", stdout);

  int N, M;
  cin >> N >> M;
  assert(1 <= N && N <= 50000);
  assert(1 <= M && M <= 100000);
  for(int i = 0; i < M; i++) {
    int u, v;
    cin >> u >> v;
    assert(u != v);
    assert(1 <= u && u <= N);
    assert(1 <= v && v <= N);
    u--; v--;

    E[u].push_back(v);
    E[v].push_back(u);
  }

  int ccnt = 0;
  int result = 0;
  memset(color, -1, sizeof(color));
  for(int i = 0; i < N; i++) {
    if(color[i] != -1) continue;
    ccnt++;
    colorcount[0] = colorcount[1] = 0;
    if (!dfs(i, 0)) {
      result = -1;
      break;
    }
    result += max(colorcount[0], colorcount[1]);
  }
  cout << result << endl;

  return 0;
}