查看“︁食物链”︁的源代码

老虎、狗和马，它们之间有个奇怪的“循环吃法”：<blockquote>老虎吃狗，狗吃马，马吃老虎。</blockquote>现在，森林里来了一个“神秘法官”，他把 N 只动物（编号 1~N）关在小黑屋里，你只能透过门缝听，完全看不到谁是谁。法官开始念“内部情报”：

* 情报一：<code>1 X Y</code> —— 意思是“X 和 Y 是同一个物种”（比如都是老虎）。
* 情报二：<code>2 X Y</code> —— 意思是“X 能吃掉 Y”。

你的任务就是当“鉴谎官”：每听到一句话，就判断它是否和前面已经确认的情报'''逻辑矛盾'''，要是矛盾，这就是假话。最后统计一共听到了多少句假话。

== 为什么我们不能直接“看答案”？ ==

你肯定想：“把门打开看看它是老虎还是狗不就行了？”

'''关键就在这里：'''法官永远不让你开门，而且他给的情报特别少！  
比如他说“1号吃2号，2号吃3号”，虽然不知道 1、2、3 具体是谁，但我们能铁定推出“3号一定吃1号”（因为老虎→狗→马→老虎，循环了）。这时候如果法官补一句“1号和3号是同类”，那肯定是假话——因为我们用逻辑推导出它俩是“食物链上下游”，绝不可能是同类。

所以，我们的核心思路不是去猜“1号是老虎还是狗”，而是'''只维护动物之间两两的“相对关系”'''：是同类？还是甲吃乙？

== 第一关：先忘掉“吃”，只谈“同类” ==

假设所有情报都是“X和Y是同类”，那问题就简单多了：就像在交朋友，A和B是朋友，B和C是朋友，那A和C自然也是朋友。随着情报增多，动物们会分成一个个“朋友圈”。

这时候，我们需要一个'''超级小本本'''，它能快速做到两件事：
# '''查'''（Find）：任意两只动物，查一查它们在不在同一个朋友圈？
# '''并'''（Union）：如果不在同一个朋友圈，怎么把这两个圈子快速合并成一个？

这个“超级小本本”，就是算法界大名鼎鼎的'''并查集（Union-Find）'''。你可以把它想象成'''一棵棵“家族树”'''：

* 每个朋友圈选一个“族长”（根节点），比如 1 号是族长。
* 每个成员只记录自己的“老爸”是谁（父节点 f[i]）。
* 想找族长，就顺着老爸、老爸的老爸……一路往上爬。

=== 并查集的核心操作 ===

'''1. 查询族长（Find）——加上“路径压缩”''' 

如果一条链特别长（1是族长，2挂1，3挂2，4挂3……），找4的族长要爬三层，太慢了！  
所以我们的绝招是：'''在找族长的时候，顺手把沿途所有人的老爸直接改成族长'''。下次再找，一步到位！

<source lang="c++" line="1">
int find(int x) {
    if (f[x] == x) return x;    // 我自己就是族长
    return f[x] = find(f[x]);   // 路径压缩：直接把老爸改成族长
}
</source>

'''2. 合并圈子（Union）——加上“按秩合并”''' 

如果两个圈子要合并，该让哪个圈子的族长当新族长呢？如果总把大树挂在小树上，树会越来越高。  

所以我们记录每棵树的高度（rank），'''总是把矮的树挂到高的树下面'''，这样树的高度增长最慢，整体更扁平。

<source lang="c++" line="1">
void union(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return;
    if (rank[ra] < rank[rb]) swap(ra, rb); // 让ra当新族长
    f[rb] = ra;                             // rb挂到ra下面
    if (rank[ra] == rank[rb]) rank[ra]++;  // 高度一样时，新高度+1
}
</source>

有了路径压缩和按秩合并，并查集的速度就快到飞起（几乎是常数时间 O(α(N))），处理几万只动物绰绰有余。

== 第二关：加入“吃”的关系——带上“权值”的小本本 ==

现在问题升级了，圈子里不仅有“同类”，还有“上级”和“下级”（吃与被吃）。普通并查集只记录“连不连”，现在我们要记录'''“连着的这条线是什么关系”'''。

于是，我们给并查集的每条边贴上一个'''标签（权值）dis[i]'''，表示 i 和它的老爸 f[i] 之间的关系。我们用数字 0、1、2 来定义：

* '''0'''：我和老爸是同类。
* '''1'''：'''老爸吃我'''。（重点！代码里就是这么定义的，记牢它）
* '''2'''：'''我吃老爸'''。

为什么要用 0、1、2？因为三种关系首尾相连（0→同类，1→老爸吃我，2→我吃老爸），正好可以用'''模 3（%3）加法'''来传递。比如：如果老爸吃我（1），老爸的老爸吃老爸（1），那我到爷爷的关系就是 (1+1)%3 = 2，表示我吃爷爷。完美契合循环食物链！

=== 带权并查集的“查”（Find）——边压缩边算账 ===

在找族长（根节点）的路上，我们要把沿途的权值累加起来，这样就能知道'''我和族长是什么关系'''。

<source lang="c++" line="1">int find(int x) {
    if (f[x] == x) return x;
    int fa = f[x];           // 记下老爸
    int root = find(fa);     // 递归找到族长（同时更新了dis[fa]）
    dis[x] = (dis[x] + dis[fa]) % 3; // 累加关系：我到老爸 + 老爸到爷爷
    return f[x] = root;      // 路径压缩，挂到族长下面
}</source>

=== 带权并查集的“并”（Union）——最精彩的公式推导 ===

现在，我们听到一句新情报：“X 和 Y 的关系是 d”（d=0 代表同类，d=1 代表 X 吃 Y）。

'''第一步：找族长'''  找到 X 的族长 fx，Y 的族长 fy。  
如果 fx == fy，说明它们已经在同一本账上了，我们直接算一下 X 和 Y 的实际关系，跟 d 比对，对不上就是假话（后面细说）。

'''第二步：合并账本'''  如果 fx != fy，说明这句话不矛盾，是真的。我们要把两本账合并。假设我们把 fy 这棵树的族长，'''挂到 fx 下面'''（即 f[fy] = fx）。

现在最关键的问题来了：'''新挂上去的这条边，标签 dis[fy] 应该填几？'''

我们来解这个“模 3 方程”：

* 已知 dis[x] 表示 '''X 和老爸 fx 的关系'''（老爸吃我？还是我吃老爸？）。
* 已知 dis[y] 表示 '''Y 和老爸 fy 的关系'''。
* 设 dis[fy] = w，表示 '''fy 和它新老爸 fx 的关系'''。

我们要让合并后，X 和 Y 的关系正好等于 d（d=1 时 X 吃 Y）。

根据我们的定义，'''任意两个动物 a 和 b 的关系（a 吃 b 则值为1）'''，可以用公式计算：<code>a 到 b 的关系 = (dis[b] - dis[a] + 3) % 3</code>

所以，X 到 Y 的关系等于：<code>(dis[y] 到 fx的关系 - dis[x] + 3) % 3</code>

而 Y 到 fx 的关系，就是 Y 先到 fy，再从 fy 到 fx：
<code>(dis[y] + dis[fy]) % 3</code>

代入得到：
<code>((dis[y] + w) - dis[x]) % 3 = d</code>

解这个方程（把 w 挪到一边）：
<code>w = (dis[x] - dis[y] + d + 3) % 3</code>

'''看！这就是参考答案里那行公式 <code>dis[fb] = (3 + dis[a] - dis[b] + d) % 3</code> 的由来！''' 它完全不是凭空出现的，而是逻辑推导的必然结果。

== 第三关：如何当场判定假话？ ==
每次听到一句话，我们按以下顺序排查：

# '''硬伤'''：如果 X 或 Y 编号大于 N 或者小于等于 0，直接算假话（范围外不存在）。
# '''自己吃自己'''：如果 op == 2 且 X == Y，直接算假话（动物不能自己吃自己，但自己和自己同类是真话）。
# '''逻辑冲突'''（已经在同一个集合中）：
   * 如果是“同类”（op=1）：检查 dis[x] 是否等于 dis[y]。如果不等，说明它们对族长的关系不同，不可能是同类，假话！
   * 如果是“X吃Y”（op=2）：计算 X 到 Y 的实际关系 (dis[y] - dis[x] + 3) % 3，看它是否等于 1。如果不等于 1，假话！

如果以上都没问题，这句话就是真话，执行 merge 操作，把两个集合连起来。
== 回头看看代码，是不是全懂了？ ==

最后，我们带着满满的成就感，再看一遍参考答案：

<source lang="cpp">
#include <bits/stdc++.h>
#define MAXN 50005
using namespace std;
int n, k, f[MAXN], dis[MAXN], x, y, op, ans;
int find(int x)
{
  if (f[x] == x)
    return x;
  int fa = find(f[x]);
  dis[x] = (dis[x] + dis[f[x]]) % 3;
  return f[x] = fa;
}
void merge(int d, int a, int b)
{
  int fa = find(a), fb = find(b);
  if (fa == fb)
    return;
  dis[fb] = (3 + dis[a] - dis[b] + d) % 3;
  f[fb] = fa;
}
int main()
{
#ifndef ONLINE_JUDGE
  freopen("data/data1.in", "r", stdin);
// freopen("data/data1.out", "w", stdout);
#endif
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++)
    f[i] = i;
  while (k--)
  {
    scanf("%d%d%d", &op, &x, &y);
    if (x > n || x <= 0 || y > n || y <= 0)
    {
      ans++;
      continue;
    }
    if (op == 1)
    {
      if (find(x) == find(y))
        ans += dis[x] != dis[y];
      else
        merge(op - 1, x, y);
    }
    else
    {
      if (find(x) == find(y))
        ans += (dis[y] - dis[x] + 3) % 3 != 1;
      else
        merge(op - 1, x, y);
    }
  }
  printf("%d", ans);
  return 0;
}
</source>

* f 数组是“家族树”的骨架。
* dis 数组是“家族树”边上的关系标签。
* find 函数里的递归，是在“寻根问祖”的同时“清理门户”（路径压缩+权值更新）。
* merge 里的公式，是在两个陌生的家族之间，找到唯一正确的“联姻方式”。

'''并查集'''就像一位精明的档案管理员，用“路径压缩”让查档案快如闪电，用“按秩合并”让档案柜永远整整齐齐。而'''带权并查集'''，则是给每份档案贴上了“关系标签”，让老虎、狗、马之间的恩恩怨怨，都在 0、1、2 的模 3 运算中灰飞烟灭。

现在，打开你的编辑器，亲手敲一遍吧。当代码跑出正确答案的那一刻，你收获的不仅仅是一道题的通过，更是一种将“复杂关系”抽象成“数学运算”的神奇思维。