Apkqiu：替换source为新的syntaxhighlight

2026-08-19T12:09:50Z

替换source为新的syntaxhighlight

←上一版本		2026年8月19日 (三) 12:09的版本
第36行：		第36行：
	所以我们的绝招是：'''在找族长的时候，顺手把沿途所有人的老爸直接改成族长'''。下次再找，一步到位！		所以我们的绝招是：'''在找族长的时候，顺手把沿途所有人的老爸直接改成族长'''。下次再找，一步到位！

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

	'''2. 合并圈子（Union）——加上“按秩合并”'''		'''2. 合并圈子（Union）——加上“按秩合并”'''
第49行：		第49行：
	所以我们记录每棵树的高度（rank），'''总是把矮的树挂到高的树下面'''，这样树的高度增长最慢，整体更扁平。		所以我们记录每棵树的高度（rank），'''总是把矮的树挂到高的树下面'''，这样树的高度增长最慢，整体更扁平。

	<~~source~~ lang="c++" line="1">		<syntaxhighlight lang="c++" line="1">
	void union(int a, int b) {		void union(int a, int b) {
	int ra = find(a), rb = find(b);		int ra = find(a), rb = find(b);
第57行：		第57行：
	if (rank[ra] == rank[rb]) rank[ra]++; // 高度一样时，新高度+1		if (rank[ra] == rank[rb]) rank[ra]++; // 高度一样时，新高度+1
	}		}
	</~~source~~>		</syntaxhighlight>

	有了路径压缩和按秩合并，并查集的速度就快到飞起（几乎是常数时间 O(α(N))），处理几万只动物绰绰有余。		有了路径压缩和按秩合并，并查集的速度就快到飞起（几乎是常数时间 O(α(N))），处理几万只动物绰绰有余。
第77行：		第77行：
	在找族长（根节点）的路上，我们要把沿途的权值累加起来，这样就能知道'''我和族长是什么关系'''。		在找族长（根节点）的路上，我们要把沿途的权值累加起来，这样就能知道'''我和族长是什么关系'''。

	<~~source~~ lang="c++" line="1">int find(int x) {		<syntaxhighlight lang="c++" line="1">int find(int x) {
	if (f[x] == x) return x;		if (f[x] == x) return x;
	int fa = f[x]; // 记下老爸		int fa = f[x]; // 记下老爸
第83行：		第83行：
	dis[x] = (dis[x] + dis[fa]) % 3; // 累加关系：我到老爸 + 老爸到爷爷		dis[x] = (dis[x] + dis[fa]) % 3; // 累加关系：我到老爸 + 老爸到爷爷
	return f[x] = root; // 路径压缩，挂到族长下面		return f[x] = root; // 路径压缩，挂到族长下面
	}</~~source~~>		}</syntaxhighlight>

	=== 带权并查集的“并”（Union）——最精彩的公式推导 ===		=== 带权并查集的“并”（Union）——最精彩的公式推导 ===
第133行：		第133行：
	最后，我们带着满满的成就感，再看一遍参考答案：		最后，我们带着满满的成就感，再看一遍参考答案：

	<~~source~~ lang="cpp">		<syntaxhighlight lang="cpp">
	#include <bits/stdc++.h>		#include <bits/stdc++.h>
	#define MAXN 50005		#define MAXN 50005
第189行：		第189行：
	return 0;		return 0;
	}		}
	</~~source~~>		</syntaxhighlight>

	* f 数组是“家族树”的骨架。		* f 数组是“家族树”的骨架。

Apkqiu：创建页面，内容为“老虎、狗和马，它们之间有个奇怪的“循环吃法”：
老虎吃狗，狗吃马，马吃老虎。
现在，森林里来了一个“神秘法官”，他把 N 只动物（编号 1~N）关在小黑屋里，你只能透过门缝听，完全看不到谁是谁。法官开始念“内部情报”： * 情报一：`1 X Y` —— 意思是“X 和 Y 是同一个物种”（比如都是老虎）。 * 情报二：`2…”`


2026-08-19T09:53:55Z
创建页面，内容为“老虎、狗和马，它们之间有个奇怪的“循环吃法”：<blockquote>老虎吃狗，狗吃马，马吃老虎。</blockquote>现在，森林里来了一个“神秘法官”，他把 N 只动物（编号 1~N）关在小黑屋里，你只能透过门缝听，完全看不到谁是谁。法官开始念“内部情报”：  * 情报一：<code>1 X Y</code> —— 意思是“X 和 Y 是同一个物种”（比如都是老虎）。 * 情报二：<code>2…”
新页面
老虎、狗和马，它们之间有个奇怪的“循环吃法”：<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 运算中灰飞烟灭。



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

食物链 - 版本历史

Apkqiu：​替换source为新的syntaxhighlight

Apkqiu：替换source为新的syntaxhighlight