题意：学生和课程构成二部图，然后需要找到一个集合每个学生代表一门课，每一门课有一个学生代表。
思路：二分图入门题。当最大匹配等于课程数的时候可以找到集合。
代码如下：
1 /************************************************** 2 * Author : xiaohao Z 3 * Blog : http://www.cnblogs.com/shu-xiaohao/ 4 * Last modified : 2014-02-20 17:48 5 * Filename : poj_1469.cpp 6 * Description : 7 * ************************************************/ 8 9 #include <iostream> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <cmath> 14 #include <algorithm> 15 #include <queue> 16 #include <stack> 17 #include <vector> 18 #include <set> 19 #include <map> 20 #define MP(a, b) make_pair(a, b) 21 #define PB(a) push_back(a) 22 23 using namespace std; 24 typedef long long ll; 25 typedef pair<int, int> pii; 26 typedef pair<unsigned int,unsigned int> puu; 27 typedef pair<int, double> pid; 28 typedef pair<ll, int> pli; 29 typedef pair<int, ll> pil; 30 31 const int INF = 0x3f3f3f3f; 32 const double eps = 1E-6; 33 const int LEN = 1010; 34 vector<int> Map[LEN]; 35 int n, match[LEN], vis[LEN]; 36 37 bool dfs(int u){ 38 vis[u] = 1; 39 for(int i=0; i<Map[u].size(); i++){ 40 int v = Map[u][i], w = match[v]; 41 if((!vis[w] && dfs(w)) || w < 0){ 42 match[u] = v; 43 match[v] = u; 44 return true; 45 } 46 } 47 return false; 48 } 49 50 int hungary() 51 { 52 int ret = 0; 53 memset(match, -1, sizeof match); 54 for(int i=0; i<n; i++){ 55 if(match[i] >= 0) continue; 56 memset(vis, 0, sizeof vis); 57 if(dfs(i)) ret ++; 58 } 59 return ret; 60 } 61 62 int main() 63 { 64 // freopen("in.txt", "r", stdin); 65 66 int T, stu, cr, b; 67 scanf("%d", &T); 68 while(T--){ 69 for(int i=0; i<LEN; i++) Map[i].clear(); 70 scanf("%d%d", &cr, &stu); 71 for(int i=0; i<cr; i++){ 72 int tn; 73 scanf("%d", &tn); 74 for(int j=0; j<tn; j++){ 75 scanf("%d", &b); 76 b--; 77 Map[i].PB(cr+b); 78 Map[cr+b].PB(i); 79 } 80 } 81 n = cr + stu; 82 int ans = hungary(); 83 if(ans == cr) printf("YES "); 84 else printf("NO "); 85 } 86 return 0; 87 }