BZOJ1997 Planer < 2-SAT >

Problem

Planer

Description


Input


Output


Sample Input

2 
6 9 
1 4 
1 5 
1 6 
2 4 
2 5 
2 6 
3 4 
3 5 
3 6 
1 4 2 5 3 6 
5 5 
1 2 
2 3 
3 4 
4 5 
5 1 
1 2 3 4 5

Sample Output

NO
YES

标签：2-SAT 并查集

Solution

本题和$POJ3207$没什么区别…
只是刚做$POJ3207$时是复习$2-SAT$，所以写了$tarjan$，然而某天碰到这题突然想到了并查集。
貌似此题可以种类并查集$trick$过。
把每条线段拆成两个点，代表从里面连和外面连，对于相交线段$a,b$，一定有$a$和$b$不同时在里面或外面，于是$merge(a, b')$, $merge(a', b)$。这样合并时判断是否有$i$, $i'$在同一集中即可。

Code

#include <iostream>
#include <cstdio>
#define MAX_N 200
#define MAX_M 10000
using namespace std;
int n, m, p[MAX_N+5], l[MAX_M+5], r[MAX_M+5], fa[MAX_M*2+5];
void init() {for (int i = 0; i < 2*m; i++)    fa[i] = i;}
int getf(int x) {return fa[x] == x ? x : fa[x] = getf(fa[x]);}
void merge(int a, int b) {a = getf(a), b = getf(b);    if (a != b)	fa[a] = b;}
int main() {
    int T;	scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m), init();	bool flag = true;
        for (int i = 0; i < m; i++)	scanf("%d%d", &l[i], &r[i]);
        for (int i = 0, x; i < n; i++)	scanf("%d", &x), p[x] = i;
        for (int i = 0; i < m; i++)	l[i] = p[l[i]], r[i] = p[r[i]];
        for (int i = 0; i < m; i++)	if (l[i] > r[i])	swap(l[i], r[i]);
        for (int i = 1; i < m; i++)	for (int j = 0; j < i; j++)
            if ((l[i] < l[j] && r[i] > l[j] && r[i] < r[j]) || (l[i] > l[j] && l[i] < r[j] && r[i] > r[j]))
                merge(i*2, j*2+1), merge(i*2+1, j*2);
        for (int i = 0; i < m; i++)	flag &= (getf(i*2) != getf(i*2+1));
        printf("%s\n", flag ? "YES" : "NO");
    }
    return 0;
}