和以前做过的一个二分图颇为相似,以前的是互相不认识的放在一组,这个是互相认识的,本质上是相同的
是 hdu 2444
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
#define cl(a) memset(a,0,sizeof(a))
#define ts printf("*****\n");
#define MAXN 202
vector<int>EV[MAXN];
int linker[MAXN];
bool used[MAXN];
int uN;
int matchs[MAXN],cnt[MAXN];
bool dfs(int u)
{
int i;
for(i=;i<EV[u].size();i++)
{
int v=EV[u][i];
if(!used[v])
{
used[v]=true;
if(linker[v]==-||dfs(linker[v]))
{
linker[v]=u;
return true;
}
}
}
return false;
}
int hungary()
{
int res=;
int u;
memset(linker,-,sizeof(linker));
for(u=;u<=uN;u++)
{
memset(used,false,sizeof(used));
if(dfs(u)) res++;
}
return res;
}
bool judge(int x,int y) //交叉染色法判断二分图
{
int i;
for(i=;i<EV[x].size();i++)
{
if(cnt[EV[x][i]]==)
{
cnt[EV[x][i]]=-*y;
matchs[EV[x][i]]=true;
if(!judge(EV[x][i],-*y)) return false;
}
else if(cnt[EV[x][i]]==y) return false;
}
return true;
}
bool matched()
{
int i;
memset(matchs,false,sizeof(matchs));
for(i=;i<=uN;i++)
{
if(EV[i].size()&&!matchs[i])
{
memset(cnt,,sizeof(cnt));
cnt[i]=-;
matchs[i]=true;
if(!judge(i,-)) return false;
}
}
return true;
}
int g[MAXN][MAXN];
int main()
{
int m,n;
int i,j;
int u,v;
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
while(scanf("%d",&uN)!=EOF)
{
n=uN;
for(i=;i<=uN;i++)
if(EV[i].size()) EV[i].clear();
cl(g);
int id;
for(i=;i<=n;i++)
{
while(scanf("%d",&id)!=EOF&&id)
{
g[i][id]=;
}
}
for(i=;i<=n;i++)
{
for(j=i+;j<=n;j++)
{
if(!g[i][j]||!g[j][i])
{
EV[i].push_back(j);
EV[j].push_back(i);
}
}
}
if(matched())
printf("YES\n");
else printf("NO\n");
}
return ;
}