当前位置: 首页 > news >正文

2-SAT模板

image

image

洛谷p4782

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=2e6+10;
int n,m;
int dfn[N],low[N],stk[N],instk[N],tot,cnt,scc[N],top;
vector<int> edges[N];void tarjan(int u){dfn[u]=low[u]=++tot;stk[++top]=u;instk[u]=1;for(int &v:edges[u]){if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if(instk[v]){low[u]=min(low[u],dfn[v]);}}if(low[u]==dfn[u]){int v;cnt++;do{v=stk[top--];instk[v]=0;scc[v]=cnt;}while(v^u);}
}int main(){cin.tie(nullptr)->sync_with_stdio(false);cin>>n>>m;while(m--){int i,a,j,b;cin>>i>>a>>j>>b;edges[i+!a*n].push_back(j+b*n);edges[j+!b*n].push_back(i+a*n);}for(int i=1;i<=n+n;i++){if(!dfn[i]){tarjan(i);}}for(int i=1;i<=n;i++){if(scc[i]==scc[i+n]){cout<<"IMPOSSIBLE"<<endl;return 0;}}cout<<"POSSIBLE"<<endl;for(int i=1;i<=n;i++){cout<<(scc[i]>scc[i+n])<<' ';}return 0;
}
http://www.hskmm.com/?act=detail&tid=25153

相关文章:

  • lab5
  • lab4
  • NumPy广播:12个技巧替代循环,让数组计算快40倍
  • 某中心2026年推出1111个技术实习岗位
  • 川土微变频器应用分享
  • POLIR-Society-Philosophy- Hegels 形而上学System Philosophy Dialectics 系统化哲学辩证法: 自由意志+封闭的绝对精神
  • 解决VLC 无法解码格式“h264” (H264 - MPEG-4 AVC (part 10))
  • CF2115 总结
  • luogu P8816 [CSP-J 2022] 上升点列 题解
  • CF558C Amr and Chemistry BFS解
  • Atbash密码和摩斯密码
  • Redis 中如何保证缓存与数据库的内容一致性?
  • Payload CMS:开发者优先的Next.js原生开源解决优秀的方案,重新定义无头内容管理
  • 第一次写博客
  • 07. 自定义组件
  • python语法记录
  • 2025 年储罐厂家推荐最新公司权威排行榜榜单发布,深度解析衬四氟储罐 / 硫酸储罐 / 盐酸储罐工厂选购指南
  • UnicodeEncodeError: locale codec cant encode character \u5e74 in position 2: encoding error
  • 2025 年生物除臭设备厂家最新推荐排行榜:覆盖污水处理厂 / 垃圾中转站等多场景,助力企业精准挑选优质设备
  • 2025 年球墨铸铁管公司:重庆南恩物资全品类管材供应与市政工程适配解决方案解析
  • 2025生物除臭设备厂家最新品牌企业推荐排行榜揭晓:印染厂污水,食品厂污水,污水处理厂,污水泵站,污水站,餐厨垃圾,屠宰场,厨余垃圾生物除臭设备公司推荐
  • 2025 工业加热器选型必看:六大加热器实力厂家深度推荐,覆盖多场景加热设备解决方案
  • YOLO模型部署
  • 从理念到沙盘:用悟空博弈模拟器点亮人机共治的曙光
  • 深入解析:Redis事务详解:原理、使用与注意事项
  • phone num
  • Perplexity发布搜索API,驱动下一代AI应用开发
  • PWN手的成长之路-09-SWPUCTF 2023 秋季新生赛Shellcode
  • 20251005 总结
  • OKR1