P9869 | 你真的会基环树找环吗

· · 题解

full version

你真的会写基环树找环吗？

考虑对于每次直接赋值操作 a\gets b，从 b 向 a 连一条 有向红边；对于每次取反后赋值操作 c\gets \lnot d，从 d 向 c 连一条 有向黑边。对于赋值成 \text{T,F,U} 的情况，直接建立对应虚点即可。

发现这样不太好处理一个点被多次赋值的情况；考虑每次赋值操作，均把 被赋值点 复制一份（也可以理解为新增一个版本）。这样，每一个点均代表了一个唯一的 \text{tribool} 值。

同时为了满足「初末值相同」的需求，我们从每个点的最后版本直接向初值所对应的版本连一条 有向红边，表示末值可以「推导」出初值，且两者相同。

容易发现，这样处理完后，每个点入度均为 1，构成了一棵 外向基环树。

考虑什么情况下会出现 \text{U}。

  2. 基环树环上存在 奇数条黑边。这意味着如果从环上某一点出发，转一圈回来后的值恰好等于初值 取反 后的值。同样整棵树也应该是 \text{U}。

基环树找环即可，时间复杂度 O(\sum n+m)。

constexpr ll MAXN = 2e5 + 5;
int n, m, cur[MAXN], cnt, val[MAXN], bl[MAXN]; // val: 1-T, 2-F, 3-U; cur: 每个点最新版本的编号
vector<pair<int, bool>> G[MAXN], G2[MAXN];
bitset<MAXN> vis, onC;
vector<vector<int>> cycle;
stack<int> st;
bool ok = 0;
void dfs(int x, int rt) {
  if (bl[x] == rt) {
    while (1) {
      int u = st.top();
      st.pop();
      onC[u] = 1, cycle.back().eb(u);
      if (u == x)
        break;
    }
    return ok = 1, void();
  } else if (!G2[x].size()) {
    onC[x] = 1;
    cycle.back().eb(x);
    return ok = 1, void();
  }
  st.push(x);
  vis[x] = 1, bl[x] = rt;
  for (pii e : G2[x]) {
    if (ok)
      return;
    dfs(e.fi, rt);
  }
}
il void addEdge(int u, int v, int w) {
  G[u].eb(v, w);
  G2[v].eb(u, w);
}
il void dfs2(int x, bool tp) {
  val[x] = tp ? 3 : 0, vis[x] = 1;
  for (pii e : G[x]) {
    if (!onC[e.fi]) {
      dfs2(e.fi, tp);
    }
  }
}
il void calc() { // 找环
  int cur = 0, hasC = 0;
  bool qwq = 0;
  for (int x : cycle.back()) {
    hasC |= (x == n + m + 3);
    if (x == n + m + 1 && !qwq && cur) {
      qwq = 1;
    } else if (x == n + m + 2 && !qwq && !cur) {
      qwq = 1;
    }
    for (pii e : G[x]) {
      if (onC[e.fi]) {
        cur ^= e.se;
        break;
      }
    }
  }
  for (int x : cycle.back()) {
    dfs2(x, cur || hasC); // 染色
  }
}
il void solve() {
  read(n, m);
  int A = n + m + 1, B = n + m + 2, C = n + m + 3; // T, F, U 对应虚点
  cnt = n, vis.reset(), onC.reset();
  fill(bl + 1, bl + C + 1, 0);
  fill(val + 1, val + C + 1, 0);
  cycle.clear();
  For(i, 1, n + m + 3) G[i].clear(), G2[i].clear();
  iota(cur + 1, cur + 1 + n, 1);
  For(i, 1, m) {
    char op[3];
    int x, y;
    scanf("%s%d", op, &x);
    if (op[0] == '+') {
      scanf("%d", &y);
      addEdge(cur[y], ++cnt, 0), cur[x] = cnt;
    } else if (op[0] == '-') {
      scanf("%d", &y);
      addEdge(cur[y], ++cnt, 1), cur[x] = cnt;
    } else {
      if (op[0] == 'T') {
        addEdge(A, (cur[x] = ++cnt), 0);
      } else if (op[0] == 'F') {
        addEdge(B, (cur[x] = ++cnt), 0);
      } else {
        addEdge(C, (cur[x] = ++cnt), 0);
      }
    }
  }
  assert(cnt == n + m);
  cnt += 3;
  For(i, 1, n) addEdge(cur[i], i, 0);
  For(i, 1, cnt) if (!vis[i]) {
    while (!st.empty())
      st.pop();
    ok = 0;
    cycle.eb();
    dfs(i, i);
    assert(ok);
    calc();
  }
  int ans = 0;
  For(i, 1, n) { ans += val[i] == 3; } // 末值被染成 U
  cout << ans << endl;
}
il void Main() {
  int c, T;
  freopen("tribool.in", "r", stdin);
  freopen("tribool.out", "w", stdout);
  read(c, T);
  while (T--)
    solve();
}