题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1068
/*最大独立集问题(等于 定点数 - 最大匹配数) 题目大意为: 大学二年级的时候,一些同学开始研究男女同学之间的缘分。研究者试图找出没有 缘分同学的最大集。程序的结果就是要输出这个集合中学生的数量 */ #include <iostream> using namespace std; const int MAX = 500; bool visited[MAX]; bool linked[MAX][MAX]; int arossPath[MAX]; int n; bool search(int u) { for (int i = 0; i < n; i++) { if (!visited[i]&& linked[i][u]) { visited[i] = true; if (arossPath[i] == -1 || search(arossPath[i])) { arossPath[i] = u;//取反 return true; } } } return false; } int maxMatch() { int count = 0; memset(arossPath, -1, sizeof(arossPath)); for (int i = 0; i < n; i++) { memset(visited, false, sizeof(visited)); if (search(i)) count++; } return count; } int main() { int k, a, b; while (scanf("%d", &n) != EOF) { memset(linked, false, sizeof(linked)); for (int i = 0; i < n; i++) { scanf("%d: (%d)", &a, &k); while (k--) { scanf("%d", &b); linked[a][b] = true; } } cout << (n - maxMatch()/2) << endl;//由于为双向,要除以二 } return 0; }