Tag-2-SAT

Icontofig 's Blog // 我们的征程是星辰大海！Away From OI，Come to ICPC（查看友链请点About Me）

2-SAT问题

2-SAT问题一般会给出n个布尔变量（取0或1），再给出m个限制条件，求问是否能够找到可行性解满足这些约束条件。

约束条件建图方式

1.必选${x}_{i}$$x_i$:从${i}^{\prime }$$i'$$i$$i$连一条有向边，表示推出${i}^{\prime }$$i'$为1是必然推出$i$$i$为1，保证${x}_{i}$$x_i$=true。
2.必不选${x}_{i}$$x_i$：从${i}^{\prime }$$i'$$i$$i$连一条有向边。
3.${x}_{i}$$x_i$${x}_{j}$$x_j$中至少选一个（${x}_{i}$$x_i$ or ${x}_{j}$$x_j$ = 1）：连接边${j}^{\prime }$$j'$->$i$$i$,${i}^{\prime }$$i'$->$j$$j$
4.${x}_{i}$$x_i$${x}_{j}$$x_j$中不能都选（${x}_{i}$$x_i$ and ${x}_{j}$$x_j$ = 0）：连接边$j$$j$->${i}^{\prime }$$i'$,$i$$i$->${j}^{\prime }$$j'$
5.${x}_{i}$$x_i$${x}_{j}$$x_j$选择情况相同（${x}_{i}$$x_i$ xor ${x}_{j}$$x_j$ = 0）：

6.${x}_{i}$$x_i$${x}_{j}$$x_j$选择情况相反（${x}_{i}$$x_i$ xor ${x}_{j}$$x_j$ = 1）：

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