hdu4715
2024-08-28 17:42:00
题解:
二分图判断
建立原图的补图
判断是否是二分图
代码:
#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");
}
}
最新文章
- 类别(Category)与扩展(Extensions)
- BZOJ 1024 【SCOI2009】 生日快乐
- EF分页中的陷阱
- Acunetix Web漏洞扫描器
- hdu Turn the corner
- iOS-网址集
- android 入门 006(sqlite增删改查)
- C++ 出现bug :二位数组的操作运算,求非对角线的元素的和
- Java反射的理解
- <;一>;初探js特效魅力之选项卡05
- UVa 202 - Repeating Decimals
- 禁止页面复制功能 js禁止复制 禁用页面右键菜单
- IE6滤镜在实战测试中能让父层里面的子元素产生阴影
- Java面试15|网络
- SqlServer存储过程及函数
- 连接SQL Server数据库
- highcharts 大数据 String+,StringBuilder,String.format运行效率比较
- 漂亮数组 Beautiful Array
- 单点登录SSO+鉴权
- java 正则 贪婪匹配 匹配sql语句中的引号内容
热门文章
- node.js基本工作原理及流程
- BeanUtils.copyProperties()
- composer 常用包管理工具
- unix 全缓冲、行缓冲、无缓冲
- 访问url
- 一个简单的仿 Launcher 应用
- maven项目中如何创建web.xml
- 使用POI做的一个生成Excel的工具类。包含了导出Excel和解析Excel方法
- 20145235李涛《网络对抗》Exp2 后门原理与实践
- react-native run-android Starting: Intent Error type 3 Error: Activity class does not exist