需求理解
你现在需要解决的是这个马戏团安排猫和狗表演、最大化观众人数的问题，核心是找到一种选猫和狗出场的方案，让尽可能多的观众满足 “想看的出场、不想看的不出场” 的条件。
问题分析
1. 核心矛盾：观众之间的冲突
首先要明确观众冲突的定义：
观众分为两类：
猫派观众（记为类型 C）：想看某只猫，不想看某只狗（格式：Cx Dy）
狗派观众（记为类型 D）：想看某只狗，不想看某只猫（格式：Dx Cy）
两个观众冲突的条件：无法同时满足两人的要求。比如：
观众 A 是 C1 D2（想看猫 1，不想看狗 2），观众 B 是 D2 C1（想看狗 2，不想看猫 1）→ 两人冲突（A 要狗 2 不出、猫 1 出；B 要狗 2 出、猫 1 不出，无法共存）；
观众 A 是 C1 D2，观众 B 是 C1 D3 → 两人不冲突（选猫 1 出场、狗 2 和 3 都不出即可同时满足）。
2. 问题转化：二分图最大独立集
这个问题本质是二分图的最大独立集问题，原因如下：
二分图的构建：
把所有观众分成左右两部分：左边是猫派观众，右边是狗派观众；
若猫派观众 A 和狗派观众 B 冲突（无法同时满足），则在 A 和 B 之间连一条边。
最大独立集的含义：在二分图中选出最多的顶点，使得这些顶点之间没有边相连（即选出的观众彼此不冲突），这正是我们要找的 “最多能满足的观众数”。
3. 关键定理
二分图有一个核心定理：最大独立集总顶点数最大匹配数因此，解决问题的核心步骤就变成：
构建猫派 - 狗派的冲突二分图；
求这个二分图的最大匹配数；
用总观众数减去最大匹配数，得到答案。
具体解题思路
步骤 1：分类观众
遍历所有 k 个观众，将他们分为两类：
猫派列表（cat_audience）：想看猫、不想看狗的观众；
狗派列表（dog_audience）：想看狗、不想看猫的观众。
步骤 2：构建冲突图（邻接表）
遍历每一个猫派观众 A，再遍历每一个狗派观众 B，判断是否冲突：冲突条件（同时满足）：
A 想看的动物 = B 不想看的动物；
A 不想看的动物 = B 想看的动物。比如：A：C1 D2 → 想看 C1，不想看 D2；B：D2 C1 → 想看 D2，不想看 C1；→ C1 = B 不想看的 C1，D2 = B 想看的 D2 → 冲突，在 A 和 B 之间连边。
步骤 3：求二分图的最大匹配
这里可以用经典的匈牙利算法（Hungarian Algorithm），专门解决二分图最大匹配问题，时间复杂度为 O (VE)（V 是顶点数，E 是边数），对于 k≤1000 的场景完全够用。
步骤 4：计算答案
根据定理：答案总观众数二分图最大匹配数
关键细节解释
1. 为什么是最大独立集？
独立集：集合内的观众彼此不冲突，即可以同时满足；
最大独立集：能满足的最多观众数，正是题目要求的目标。
2. 匈牙利算法的核心思想
为左边的每个节点（猫派观众）寻找匹配的右边节点（狗派观众）；
若当前节点找不到匹配，尝试 “让” 已匹配的节点换一个匹配，从而腾出位置；
最终统计能匹配的最大对数，即为最大匹配数。