CF2179F

一个二分图，特工可以选择给每个点染三个颜色。

一个人想知道怎么回到一号点，每次他只知道当前所有邻居的颜色。

想象以 1 号点为根的 BFS 生成树，每次其实是想知道哪些点是父亲，哪些点是儿子。

我们可以按照距离模三来染色，012 分别对应 rgb。

假设当前点距离一号点距离是 $k$，那么它的邻居要么是父亲（$k-1$），要么是儿子（$k+1$），所以只可能最多有两种颜色。

为什么不可能有一个距离同样是 $k$ 的邻居？根据二分图没有奇环的性质，如果有，那么这个环的大小就是 $2k+1$，不满足条件。

那么分类讨论就好了，

如果全都是一个颜色，那么这个颜色的节点便都是父亲（因为一个生成树中，一个节点可以没有儿子，但一定要有父亲）。

如果有两个颜色：

• r, g: 说明当前在 b，父亲是 g
• g, b: 说明当前在 r，父亲是 b
• r, b: 说明当前在 g，父亲是 r

参考代码：

#include <bits/stdc++.h>
#define ve vector
#define fi first
#define se second
using namespace std;
using ll = long long;
using vi = vector<int>;
using vii = vector<vector<int>>;

void fir() {
  int n, m;
  cin >> n >> m;
  vii adj(n + 1);
  ve<bool> vis(n + 1);
  vi ans(n + 1);
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
  }
  auto bfs = [&]() {
    queue<int> q;
    q.push(1);
    ans[1] = 0;
    while (!q.empty()) {
      int t = q.front();
      q.pop();
      if (vis[t])
        continue;
      vis[t] = true;
      for (auto v : adj[t]) {
        if (vis[v])
          continue;
        q.push(v);
        ans[v] = (ans[t] + 1) % 3;
      }
    }
  };
  bfs();
  for (int i = 1; i <= n; i++) {
    switch (ans[i]) {
    case 0:
      cout << 'r';
      break;
    case 1:
      cout << 'g';
      break;
    case 2:
      cout << 'b';
      break;
    }
  }
  cout << endl;
}

void sec() {
  int q;
  cin >> q;
  while (q--) {
    int c;
    cin >> c;
    string s;
    cin >> s;
    int r = 0, g = 0, b = 0;
    for (int i = 0; i < c; i++) {
      if (s[i] == 'r')
        r++;
      if (s[i] == 'g')
        g++;
      if (s[i] == 'b')
        b++;
    }
    if (r == c || g == c || b == c) {
      cout << 1 << endl;
      continue;
    }
    char ans;
    if (r == 0) {
      ans = 'b';
    } else if (g == 0) {
      ans = 'r';
    } else if (b == 0) {
      ans = 'g';
    }
    for (int i = 0; i < c; i++) {
      if (s[i] == ans) {
        cout << i + 1 << endl;
        break;
      }
    }
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string s;
  cin >> s;
  int T;
  if (s == "first") {
    cin >> T;
    while (T--)
      fir();
  } else if (s == "second") {
    cin >> T;
    while (T--)
      sec();
  }

  return 0;
}