题目1：洛谷 P2024

题意

• 有 \(n\) 个动物，每个动物都是 \(A,B,C\) 中的一种，其中 \(A\) 吃 \(B\)，\(B\) 吃 \(C\)，\(C\) 吃 \(A\)。给定两种食物链关系。

  • 第一种说法是 1 X Y，表示 \(X\) 和 \(Y\) 是同类。
  • 第二种说法是 2 X Y，表示 \(X\) 吃 \(Y\)。

• 这两种关系有 \(k\) 条，一条关系是真话满足当前的话与前面所有的真话冲突不冲突，且 \(X，Y \le n\) 且 \(X \ne Y\)。请输出假话的数量。

• \(1 \le n \le 5 \times 10^4,1 \le k \le 10^5\)。

思路

• 这道题显然是并查集。令 \(i\) 对应的集合为与动物 \(i\) 同类的动物， \(i + n\) 对应的集合为 \(i\) 吃的动物， \(i + n + n\) 对应的集合为吃 \(i\) 的动物。

• 如果当前关系为第一种，这条关系为真必须满足（为假答案数 \(+1\)，以下只考虑了第一种情况，后两种自己判一下）：

  • \(X\) 对应的集合不是 \(Y + n\) 对应的集合。
  • \(Y\) 对应的集合不是 \(X + n\) 对应的集合。

• 否则如果是真话需满足：

  • \(X\) 对应的集合不是 \(Y + n\) 对应的集合。
  • \(Y\) 对应的集合不是 \(Y\) 对应的集合。

• 如果当前关系为第一种且为真，将以下集合合并（为假答案数 \(+1\)，以下只考虑了第一种情况，后两种自己判一下）：

  • \(X\) 对应的集合不是 \(Y\) 对应的集合。
  • \(X + n\) 对应的集合不是 \(Y + n\) 对应的集合。
  • \(X + n\) 对应的集合不是 \(Y + n + n\) 对应的集合。

• 如果当前关系为第二种种且为真，将以下集合合并：

  • \(X + n\) 对应的集合不是 \(Y\) 对应的集合。
  • \(X\) 对应的集合不是 \(Y + n + n\) 对应的集合。
  • \(X + n + n\) 对应的集合不是 \(Y + n\) 对应的集合。

• 最后输出答案数即可。

• 时间复杂度

  • 并查集维护合并操作：\(O(n \times log \ n)\)。
  • \(k\) 次询问：\(O(k)\)。
  • 总时间复杂度：\(O(n \times log \ n +k)\)

const int MAXN = 5e4 + 5;

int n, q, c, op, x, y, fa[MAXN * 3];

int Find(int x){
  return (fa[x] ? fa[x] = Find(fa[x]) : x);
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> q;
  for(int i = 1; i <= q; i++){
    cin >> op >> x >> y;
    if(x > n || y > n || (x == y && op == 2)){ //特判后两种情况
      c++;
      continue;
    }
    int xa = Find(x), ya = Find(y); // x, y 对应的集合的代表
    int xb = Find(x + n), yb = Find(y + n); // x + n, y + n 对应的集合的代表
    int xc = Find(x + n + n), yc = Find(y + n + n); // x + n + n, y = n + n 对应的集合的代表
    if(op == 1){
      if(xa == yb || xb == ya){ //假话
        c++;
      }else{ //真话
        fa[xa] = (xa == ya ? 0 : ya);
        fa[xb] = (xb == yb ? 0 : yb);
        fa[xc] = (xc == yc ? 0 : yc);
      }
    }else{
      if(xa == ya || yb == xa){ //假话
        c++;
      }else{ //真话
        fa[ya] = (ya == xb ? 0 : xb);
        fa[yb] = (xc == yb ? 0 : xc);
        fa[xa] = (xa == yc ? 0 : yc);
      }
    }
  }
  cout << c;
  return 0;
}

题目2：CSES 2101

题意

• 有 \(n\) 个点，\(m\) 条无向边边和 \(q\) 组询问。每组询问给定两个点 \(x,y\)，问 \(x,y\) 在加入第几条边后两个点从不连通到连通，如果加入 \(m\) 条边后仍不连通，输出 \(-1\)。

• \(1 \le n, m, q \le 2 \times 10^5\)。

思路

• 题意简化为：第 \(i\) 的边权为 \(i\)，每组询问查询并查集建出森林后 \(x\) 到 \(x,y\) 的最近公共祖先 \(z\) 的路径上的边权最大值和 \(y\) 到 \(z\) 的路径上的边权最大值的最大值。

• 找最近公共祖先可以下操作（找最近公共祖先时可以顺便求一下答案）：

  • 若 \(x\) 的子树大小 \(\le\) \(y\) 的子树大小，\(x\) 变为 \(x\) 的父亲。否则 \(y\) 变为 \(y\) 的父亲。直到 \(x = y\)。
  • 如果 \(x\) 和 \(y\) 都是某个树的根但是还有往上走，就说明原先的 \(x,y\) 不在同一个树内。

• 时间复杂度

  • 输入 \(m\) 条道路：\(O(m)\)。
  • 并查集维护合并集合：\(O(n \times log \ n)\)。
  • \(q\) 组询问，每组询问 \(x,y\) 最多往上跳 \(log \ n\) 次，时间复杂度：\(O(q \times log \ n)\)。
  • 总时间复杂度：\(O(m + (n + q) \times log \ n)\)。