题意分析

题目给定一个无向图（学生之间的恋爱关系图），要求找出一个最大独立集（即最大的学生集合，其中任意两个学生之间没有恋爱关系）。最大独立集的大小等于总顶点数减去最大匹配数（对于二分图而言）。

关键点：

1. 输入格式：

   • 第一行是学生人数 n。
   • 接下来的 n 行，每行表示一个学生的恋爱关系，格式为 学生编号:(关系数量) 关系学生1 关系学生2 ...。
   • 示例：

     7
     0: (3) 4 5 6
     1: (2) 4 6
     2: (0)
     3: (0)
     4: (2) 0 1
     5: (1) 0
     6: (2) 0 1
     

     表示：
     • 学生 0 和学生 4, 5, 6 有恋爱关系。
     • 学生 1 和学生 4, 6 有恋爱关系。
     • 学生 2 和 3 没有恋爱关系，依此类推。

2. 输出要求：

   • 对于每个测试用例，输出最大独立集的大小（即最多可以选出多少学生，使得他们之间没有恋爱关系）。

解题思路

1. 问题转化

• 该问题可以转化为求无向图的最大独立集。
• 对于一般图，最大独立集是 NP-Hard 问题，但题目中的恋爱关系是无向的，且没有自环和重边，因此可以建模为二分图（男生和女生构成两个独立集）。
• 在二分图中，最大独立集 = 顶点总数 - 最大匹配数。

2. 匈牙利算法求最大匹配

• 采用匈牙利算法（DFS 实现）求解二分图的最大匹配。
• 算法流程：
  1. 初始化：match 数组记录每个点的匹配对象，初始为 -1。
  2. 遍历每个未匹配的点，尝试寻找增广路径：
     • 如果找到增广路径（即可以匹配），则更新 match 数组。
  3. 统计最大匹配数 res。
  4. 最大独立集 = n - res / 2（因为是无向图，匹配数会被计算两次）。

3. 代码实现

• 输入处理：
  • 使用 cin 读取学生编号和关系数量。
  • 构建邻接矩阵 g[N][N] 存储图结构。
• 匈牙利算法：
  • find(u) 函数用于 DFS 搜索增广路径。
  • 主循环遍历所有点，尝试匹配。
• 输出结果：
  • n - res / 2 即为最大独立集的大小。

代码优化思路

1. 邻接表优化：
   • 如果 n 较大（如 n ≤ 1000），邻接矩阵 g[N][N] 会占用较大空间，可以改用邻接表（但由于题目限制 n ≤ 500，邻接矩阵可行）。
2. 时间优化：
   • 匈牙利算法最坏情况是 O(n³)，但实际运行效率较高，适用于 n ≤ 500 的情况。
3. 空间优化：
   • 如果严格限制头文件，可以手动初始化数组，避免 memset。

最终结论

• 算法：匈牙利算法（DFS 实现）求二分图最大匹配。
• 关键公式：最大独立集 = n - 最大匹配数 / 2。
• 时间复杂度：O(n³)（最坏情况）。
• 空间复杂度：O(n²)（邻接矩阵存储）。

该解法在题目给定的数据范围（n ≤ 500）内可以高效运行，并正确求出最大独立集的大小。

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <set>

using namespace std;

int main() {
    // 随机数生成器
    random_device rd;
    mt19937 gen(rd());
    
    // 随机生成学生人数 (1到500之间)
    uniform_int_distribution<> student_dist(1, 500);
    int n = student_dist(gen);
    cout << n << endl;
    
    // 生成二分图的两个部分
    int size_a = n / 2;
    vector<int> group_a(size_a);
    vector<int> group_b(n - size_a);
    
    for (int i = 0; i < size_a; ++i) {
        group_a[i] = i;
    }
    for (int i = 0; i < n - size_a; ++i) {
        group_b[i] = size_a + i;
    }
    
    // 为每个学生生成恋爱关系
    vector<vector<int>> adjacency(n);
    
    // 随机生成边，确保每条边连接A组和B组的学生
    int max_edges = size_a * (n - size_a);
    uniform_int_distribution<> edge_dist(0, min(max_edges, 1000));
    int num_edges = edge_dist(gen);
    
    set<pair<int, int>> edges;
    uniform_int_distribution<> a_dist(0, size_a - 1);
    uniform_int_distribution<> b_dist(0, n - size_a - 1);
    
    while (edges.size() < num_edges) {
        int a_idx = a_dist(gen);
        int b_idx = b_dist(gen);
        int a = group_a[a_idx];
        int b = group_b[b_idx];
        
        if (edges.find({a, b}) == edges.end()) {
            edges.insert({a, b});
            adjacency[a].push_back(b);
            adjacency[b].push_back(a);
        }
    }
    
    // 输出每个学生的关系
    for (int student_id = 0; student_id < n; ++student_id) {
        vector<int>& partners = adjacency[student_id];
        int k = partners.size();
        
        // 排序确保输出顺序
        sort(partners.begin(), partners.end());
        
        cout << student_id << ": (" << k << ")";
        for (int partner : partners) {
            cout << " " << partner;
        }
        cout << endl;
    }
    
    return 0;
}