二分图染色法

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int t, m;
string u, v;

bool dfs(unordered_map<string, vector<string>>& g,
         string cur, 
         int color,
         unordered_map<string, int>& colors) {

  colors[cur] = color;
  for (const auto& nxt : g[cur]) {
    if (colors[nxt] == color) return false; // conflict
    if (!colors[nxt] && !dfs(g, nxt, -color, colors)) return false;
  }
  return true;
}

int main(void) {
  cin >> t;
  for (int i = 1; i <= t; ++i) {
    // build the undirected graph
    unordered_map<string, vector<string>> g;
    // 0: UNKNOWN, 1: RED, -1: BLUE
    unordered_map<string, int> colors;
    cin >> m;
    string start = "";
    while (m--) {
      cin >> u >> v;
      if (start == "") start = u;
      g[u].emplace_back(v);
      g[v].emplace_back(u);
    }

    printf("Case #%d: %s\n", i, dfs(g, start, 1, colors) ? "Yes" : "No");
  }
}