Tag-2-SAT

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2019-02-07 01:26:40 |  0 Comments  |  2-SAT

2-SAT问题

2-SAT问题

2-SAT问题一般会给出n个布尔变量(取0或1),再给出m个限制条件,求问是否能够找到可行性解满足这些约束条件。
我们对于2-SAT问题一般采取建图的方式,把一个点拆成两个点分别代表取true和false,然后根据限制条件建图,之后采取强连通分量的方式去寻找是否有可行性解。

约束条件建图方式

我们设其中两个变量xixj,设ij表示原变量(取1),ij表示其反变量(取0),那么有以下的约束条件及其建图方式:
1.必选xi:从ii连一条有向边,表示推出i为1是必然推出i为1,保证xi=true。
2.必不选xi:从ii连一条有向边。
3.xixj中至少选一个(xi or xj = 1):连接边j->i,i->j
4.xixj中不能都选(xi and xj = 0):连接边j->i,i->j
5.xixj选择情况相同(xi xor xj = 0):
连接边j->i,i->jj->i,i->j
6.xixj选择情况相反(xi xor xj = 1):
连接边

 2019-02-07 01:05:31 |  0 Comments  |  2-SAT tarjan topsort

BUPT校内训练&CodeChef - VRTXCOVR-Vertex Cover 2-SAT

Description

You are given an undirected graph G = (V, E) containing N nodes and M edges. The nodes are numbered from 1 to N. A subset C of V is a vertex cover if for every edge (u, v) ∈ E, at least one of u and v belong to C. Note that C = V is always a vertex cover.
Consider a partition of V into two sets A and B. It is said to be a valid partition, if the following two conditions are satisfied: A should be a vertex cover. And for each i such that 1 ≤ i ≤ n/2, nodes 2i and 2i - 1 don't belong to the same set (i.e. one belongs to set A and the other to set B).
Determine if a valid partition exists. If it exists, provide an example of one valid partition.

Input

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and M denoting the number of nodes and number of edges in the graph respectively.
Each of the following M lines contains two space-se

Title - Artist
0:00