传送门

2-sat问题,只需要判断yes或no

所以可以直接连边,缩点,判断同一组的是否在同一个块中。

 #include <cstdio>
#include <stack>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1000001 int n, m, cnt, idx, sz;
int head[N], to[N << ], next[N << ], dfn[N], low[N], belong[N];
bool ins[N], flag;
std::stack <int> s; inline void add(int x, int y)
{
to[cnt] = y;
next[cnt] = head[x];
head[x] = cnt++;
} inline void tarjan(int u)
{
int i, v;
dfn[u] = low[u] = ++idx;
ins[u] = ;
s.push(u);
for(i = head[u]; i != -; i = next[i])
{
v = to[i];
if(!dfn[v])
{
tarjan(v);
low[u] = std::min(low[u], low[v]);
}
else if(ins[v]) low[u] = std::min(low[u], dfn[v]);
}
if(low[u] == dfn[u])
{
++sz;
do
{
v = s.top();
s.pop();
ins[v] = ;
belong[v] = sz;
}while(u != v);
}
} int main()
{
int i, j, a, b, c, d;
while(~scanf("%d", &n))
{
memset(head, -, sizeof(head));
memset(ins, , sizeof(ins));
memset(dfn, , sizeof(dfn));
idx = cnt = sz = ;
while(!s.empty()) s.pop();
scanf("%d", &m);
for(i = ; i <= m; i++)
{
scanf("%d %d %d %d", &a, &b, &c, &d);
a = (a << ) + c;
b = (b << ) + d;
add(a, b ^ );
add(b, a ^ );
}
for(i = ; i < n << ; i++)
if(!dfn[i])
tarjan(i);
flag = ;
for(i = ; i < n; i++)
if(belong[i << ] == belong[(i << ) ^ ])
flag = ;
if(flag) printf("NO\n");
else printf("YES\n");
}
return ;
}

最新文章

  1. EF里Guid类型数据的自增长、时间戳和复杂类型的用法
  2. 【开源】MQTT推送服务器——zer0MqttServer(Java编写)
  3. php部分,一个用递归无限分类的方法
  4. Jquery.cookie.js 源码和使用方法
  5. 第十章实践——系统级I/O代码运行
  6. Mysql时间函数
  7. c程序设计语言_习题1-18_删除输入流中每一行末尾的空格和制表符,并删除完全是空格的行
  8. GDI+画图类Graphics的使用
  9. eclipse 找不到application选项
  10. java对String进行sha1加密
  11. Github 开源:使用控制器操作 WinForm/WPF 控件( Sheng.Winform.Controls.Controller)
  12. Codeforces Round #418 (Div. 2).C two points
  13. git pull以及git pull --rebase
  14. Zookeeper连接eclipse
  15. 基础作业 本周没上课,但是请大家不要忘记学习。 本周请大家完成上周挑战作业的第一部分:给定一个整数数组(包含正负数),找到一个具有最大和的子数组,返回其最大的子数组的和。 例如:[1, -2, 3, 10, -4, 7, 2, -5]的最大子数组为[3, 10, -4, 7, 2] 输入: 请建立以自己英文名字命名的txt文件,并输入数组元素数值,元素值之间用逗号分隔。 输出 在不删除原有文件内容
  16. string所在头文件
  17. Bash 中的特殊字符大全【转】
  18. vue中输入框聚焦,自动跳转下一个输入框
  19. hive 实现一个字段多行转一行 和 一行转多行
  20. (DFS)展开字符串 -- hdu -- 1274

热门文章

  1. nodejs on raspi
  2. 动手实现 Redux(四):共享结构的对象提高性能
  3. 设计 REST API 的13个最佳实践
  4. 第3章 接口与API设计 52条笔记
  5. Socket网络编程初探
  6. Java面试题之HashSet 的实现原理?
  7. C语言常用关键字及运算符操作---关键字
  8. JavaScript轮播图
  9. PHP安全之 register_globals
  10. 使用Spring AOP切面解决数据库读写分离