题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4751

题目大意:判断一堆人能否分成两组,组内人都互相认识。

解题思路:如果两个人不是相互认识,该两人之间连边。最终构成一张图,二分匹配。

 #include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define maxn 105
#define maxm 20010
int n,e;
bool path[][],flag;
int first[maxn],next[maxm],v[maxm];
int color[maxn];
bool vis[maxn];
void addedge(int x,int y)
{
v[e]=y;
next[e]=first[x];
first[x]=e++;
}
bool solve(int x,int now,int from)
{
int i,k;
color[x]=now;
for(i=first[x];i!=-;i=next[i])
{
k=v[i];
if(k!=from)
{
if(!color[k])
{
if(solve(k,-now,x)==false)return false;
}
if(color[k]==color[x])return false;
}
}
vis[x]=true;
return true;
}
int main()
{
int L,i;
while(scanf("%d",&n)!=EOF)
{
memset(color,,sizeof(color));
memset(vis,false,sizeof(vis));
memset(path,false,sizeof(path));
for(i=;i<=n;i++)
{
while(scanf("%d",&L),L)
path[i][L]=true;
}
memset(first,-,sizeof(first));
for(i = ; i < n;i++)
{
for(int j=i+;j<=n;j++)
{
if(!path[i][j]||!path[j][i])
{
addedge(i,j);
addedge(j,i);
}
}
}
flag=true;
for(i=;i<=n&&flag==true;i++)
if(color[i]==){
vis[i]=true;flag=solve(i,,-);
}
if(flag)printf("YES\n");
else printf("NO\n");
}
return ;
}

最新文章

  1. BMW
  2. [03]APUE:文件 I/O
  3. SharePoint 开启网站匿名访问图文详解
  4. quartz+spring 实现多任务动态定时器问题
  5. SqlSever大数据分页
  6. Redis笔记(一)Redis简介
  7. Java Hour 13 集合基础
  8. Codeforces Beta Round #5 E. Bindian Signalizing 并查集
  9. 编译LFS
  10. Netty轻量级对象池实现分析
  11. OpenLayer 3 鹰眼控件和全屏显示
  12. Javascript中Array(数组)对象常用的几个方法
  13. macOS 中使用 phpize 动态添加 PHP 扩展的错误解决方法
  14. 浏览器兼容性汇总--JavaScript篇
  15. 机器学习笔记(5) KNN算法
  16. AI学习---深度学习&amp;TensorFlow安装
  17. 如何在C#中使用Dapper(译)
  18. HTML_1
  19. 海量日志采集Flume(HA)
  20. postman发送json格式的post请求

热门文章

  1. ios-pch文件的手动添加
  2. What&#39;s the use of @ before the path defination
  3. javascript基础学习(十)
  4. Linux 删除文件夹
  5. linux svn启动和关闭(转)
  6. 『重构--改善既有代码的设计』读书笔记----Self Encapsulate Field
  7. (二)跟我一起玩Linux网络服务:BIND的自动部署(附上完整的代码)
  8. C# winform 递归选中TreeView子节点
  9. C# 跨线程访问控件
  10. php 购物车完整实现代码