http://poj.org/problem?id=1469
学生选课问题，基础匹配问题。
有p节课，n个学生，每节课可以由指定的几个学生参加，但是每个学生只能参加一节课。现在问能不能找到一些学生使得他们：
1.每个学生匹配不同的一节课
2.每节课匹配一个学生。
就是求个最大匹配，看看匹配数是不是等于课程数。如果相等不就满足要求了么.
Source Code
#include<stdio.h> #include<stdlib.h> #include<string.h> int nx, ny; // X的點數目、Y的點數目 int mx[302], my[102]; // X各點的配對對象、Y各點的配對對象 bool vy[102]; // 紀錄Graph Traversal拜訪過的點 bool adj[302][102]; // 精簡過的adjacency matrix // 以DFS建立一棵交錯樹 bool DFS(int x) { for (int y=0; y<ny; ++y) if (adj[x][y] && !vy[y]) { vy[y] = true; // 找到擴充路徑 if (my[y] == -1 || DFS(my[y])) { mx[x] = y; my[y] = x; return true; } } return false; } int bipartite_matching() { // 全部的點初始化為未匹配點。 memset(mx, -1, sizeof(mx)); memset(my, -1, sizeof(my)); // 依序把X中的每一個點作為擴充路徑的端點， // 並嘗試尋找擴充路徑。 int c = 0; for (int x=0; x<nx; ++x) // if (mx[x] == -1) // x為未匹配點，這行可精簡。 { // 開始Graph Traversal memset(vy, false, sizeof(vy)); if (DFS(x)) c++; } return c; } main() { int t,a,b,i,n,c,ans; scanf("%d",&t); while(t--) { memset(adj,0, sizeof(adj)); scanf("%d%d",&a,&b); for(i=0;i<a;i++) { scanf("%d",&n); while(n--) { scanf("%d",&c); adj[c-1][i]=1; } } nx=b;ny=a; ans=bipartite_matching(); if(ans==a) printf("YES\n"); else printf("NO\n"); } system("pause"); }