题意:有n个人,要彼此认识。选择一个集合,使得集合里的每个人相互不认识。求集合中人数的最大值。
求二分图的最大独立集。
公式:最大独立集=顶点数-最大匹配
这个题目中因为集合是一个,所以求出最大匹配数后要除以2。
#include<iostream>
#include<cstring>
#define maxn 1005
using namespace std;
int n;
int map[maxn][maxn],used[maxn],match[maxn];
void init(){
memset(map,,sizeof(map));
int x,k,y;
for (int i=;i<n;i++){
scanf("%d: (%d) ",&x,&k);
for (int j=;j<k;j++){
cin >> y;
map[x][y]=;
}
}
return ;
}
int dfs(int x){
for (int i=;i<n;i++){
if (map[i][x] && !used[i]){
used[i]=;
if (match[i]==- || dfs(match[i])){
match[i]=x;
return ;
}
}
}
return ;
}
int main(){
while (cin >> n && n){
init();
int ans=;
memset(match,-,sizeof(match));
for (int i=;i<n;i++){
memset(used,,sizeof(used));
if (dfs(i)) ans++;
}
cout << n-ans/ << endl;
}
return ;
}