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