题解:

二分图判断

建立原图的补图

判断是否是二分图

代码:

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int an[N],ans,a[N][N],n,x;
void dfs(int x,int y)
{
if (ans)return;
an[x]=y;
for (int i=;i<=n;i++)
if ((!a[x][i]||!a[i][x])&&i!=x)
{
if (an[i]&&-y!=an[i]){ans=;return;}
if (!an[i])dfs(i,-y);
}
}
int main()
{
while (~scanf("%d",&n))
{
ans=;
memset(an,,sizeof an);
memset(a,,sizeof a);
for (int i=;i<=n;i++)
for (scanf("%d",&x);x;scanf("%d",&x))a[i][x]=;
for (int i=;i<=n;i++)
if (!an[i])dfs(i,);
if (ans)puts("NO");else puts("YES");
}
}

最新文章

  1. 类别(Category)与扩展(Extensions)
  2. BZOJ 1024 【SCOI2009】 生日快乐
  3. EF分页中的陷阱
  4. Acunetix Web漏洞扫描器
  5. hdu Turn the corner
  6. iOS-网址集
  7. android 入门 006(sqlite增删改查)
  8. C++ 出现bug :二位数组的操作运算,求非对角线的元素的和
  9. Java反射的理解
  10. &lt;一&gt;初探js特效魅力之选项卡05
  11. UVa 202 - Repeating Decimals
  12. 禁止页面复制功能 js禁止复制 禁用页面右键菜单
  13. IE6滤镜在实战测试中能让父层里面的子元素产生阴影
  14. Java面试15|网络
  15. SqlServer存储过程及函数
  16. 连接SQL Server数据库
  17. highcharts 大数据 String+,StringBuilder,String.format运行效率比较
  18. 漂亮数组 Beautiful Array
  19. 单点登录SSO+鉴权
  20. java 正则 贪婪匹配 匹配sql语句中的引号内容

热门文章

  1. node.js基本工作原理及流程
  2. BeanUtils.copyProperties()
  3. composer 常用包管理工具
  4. unix 全缓冲、行缓冲、无缓冲
  5. 访问url
  6. 一个简单的仿 Launcher 应用
  7. maven项目中如何创建web.xml
  8. 使用POI做的一个生成Excel的工具类。包含了导出Excel和解析Excel方法
  9. 20145235李涛《网络对抗》Exp2 后门原理与实践
  10. react-native run-android Starting: Intent Error type 3 Error: Activity class does not exist