題意：有n個學生，其中他們之間某些人有聯系，問你最多能找出多少個學生組成一個集合，使得這個集合內的學生任何兩個之間沒有聯系。
思路：最大獨立集問題：在Ｎ個點的圖G中選出m個點，使這m個點兩兩之間沒有邊．求m最大值．如果圖Ｇ滿足二分圖條件，則可以用二分圖匹配來做．最大獨立集點數 = N - 最大匹配數/2，然後就是匈牙利算法實現了。
> 這個問題拆點後的二分圖為男在一邊，女的在另一邊。因此如果確定為一邊的點，就不可能於同一邊的點相連。而且由於在尋找最大匹配時不是枚舉其中一邊的點，而是枚舉兩邊的所有點，所以得到的ans為最大匹配數 的兩倍，因為每條匹配的邊都算了兩遍。
代碼：
[cpp]
<span style="font-size:18px;">#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN=125;
int uN,vN;
int map[MAXN][MAXN];
int match[MAXN];
bool visit[MAXN];
bool search(int u){
int v;
for(v=1;v<=vN;v++)
if(map[u][v]&&!visit[v]){
visit[v]=true;
if(match[v]==-1||search(match[v])){
match[v]=u;
return true;
}
}
return false;
}
int hungary(){
int res=0;
int u;
memset(match,-1,sizeof(match));
for(u=1;u<=uN;u++){
memset(visit,0,sizeof(visit));
if(search(u)) res++;
}
return res;
}
long long a[1010];
int main(){
int t;
int n;
int i, j,m,a,b;
scanf("%d", &t);
while(t --){
scanf("%d%d", &n,&m);
memset(map, 0, sizeof(map));
uN = n;
vN = n;
for(i = 0; i < m ; i ++){
scanf("%d%d",&a,&b);
map[a][b]=1;
}
int ans = n - hungary();
printf("%d\n", ans);
}
return 0;
}
</span>
