题解：P13321 [GCJ 2012 #1C] Diamond Inheritance

#include <iostream>
#include <vector>
#include <bitset>
#include <numeric>

const int MAXN = 1001; // 最大类数

std::vector<int> g[MAXN]; // 邻接表，g[u] 存储类 u 直接继承的父类列表

std::bitset<MAXN> a[MAXN]; // a[u][v] 为 true 表示类 v 是类 u 的祖先

bool v[MAXN]; // v[u] 为 true 表示类 u 的祖先已经通过 DFS 计算完毕

// 使用深度优先搜索 (DFS) 计算并填充给定类 u 的所有祖先
void d(int u) {
   // 如果已访问，直接返回
   if (v[u]) {
       return;
   }
   v[u] = true; // 标记为已访问
   a[u][u] = true; // u 是自身的祖先
   
   // 遍历所有父类
   for (int p : g[u]) {
       d(p); // 递归计算父类的祖先
       a[u] |= a[p]; // 合并父类的祖先
   }
}

// 处理单个测试用例
void s(int c) {
   int n; // 当前类图中的类总数
   std::cin >> n;

   // 初始化数据结构
   for (int i = 1; i <= n; ++i) {
       g[i].clear();        // 清空邻接表
       a[i].reset();         // 重置祖先位集
       v[i] = false;         // 重置访问标记
   }

   // 读取每个类的继承信息
   for (int i = 1; i <= n; ++i) {
       int m; // 类 i 直接继承的父类数量
       std::cin >> m;
       for (int k = 0; k < m; ++k) {
           int p; // 父类编号
           std::cin >> p;
           g[i].push_back(p); // 添加到邻接表
       }
   }

   // 为每个类计算祖先
   for (int i = 1; i <= n; ++i) {
       d(i);
   }

   bool f = false; // 是否找到菱形继承
   // 检查每个可能有多个父类的类
   for (int X = 1; X <= n; ++X) {
       // 需要至少两个父类才可能形成菱形
       if (g[X].size() < 2) {
           continue;
       }

       // 检查每对父类 (B, C)
       for (int i = 0; i < g[X].size(); ++i) {
           int B = g[X][i]; // 第一个父类
           for (int j = i + 1; j < g[X].size(); ++j) {
               int C = g[X][j]; // 第二个父类
               // 如果 B 和 C 有公共祖先
               if ((a[B] & a[C]).any()) {
                   f = true; // 发现菱形继承
                   goto end_loops; // 跳出多层循环
               }
           }
       }
   }

end_loops:; // 循环结束点
   // 输出结果
   std::cout << "Case #" << c << ": " << (f ? "Yes" : "No") << std::endl;
}

int main() {
   int t; // 测试用例总数
   std::cin >> t;
   // 处理每个测试用例
   for (int i = 1; i <= t; ++i) {
       s(i);
   }

   return 0;
}