[HDU3062]Party（2-sat）

传送门

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

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

1 #include <cstdio> 2 #include <stack> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 #define N 1000001 7 8 int n, m, cnt, idx, sz; 9 int head[N], to[N << 1], next[N << 1], dfn[N], low[N], belong[N]; 10 bool ins[N], flag; 11 std::stack <int> s; 12 13 inline void add(int x, int y) 14 19 20 inline void tarjan(int u) 21 34 else if(ins[v]) low[u] = std::min(low[u], dfn[v]); 35 } 36 if(low[u] == dfn[u]) 37 while(u != v); 46 } 47 } 48 49 int main() 50 68 for(i = 0; i < n << 1; i++) 69 if(!dfn[i]) 70 tarjan(i); 71 flag = 0; 72 for(i = 0; i < n; i++) 73 if(belong[i << 1] == belong[(i << 1) ^ 1]) 74 flag = 1; 75 if(flag) printf("NO\n"); 76 else printf("YES\n"); 77 } 78 return 0; 79 }
View Code

上一篇：[luoguP1168]中位数（主席树+离散化）

下一篇：[HNOI2009]梦幻布丁（链表+启发式合并）

---

tarjan SCC 2-sat