### Brief description :

圓環上均勻的附著著 n 個點，連接著這些點的 m 條曲線，它們或者在圓內或者在圓外。

確認是否存在一種劃分方案使得所有的曲線不相交。

### Analyse :

疑似是一種弱化的 2-SAT （無向。。）。。。

。。。是可以用並查集直接寫的吧。。

`#include `
#include
using namespace std;
const int INF = 0x7fffffff;
const int N = 1000, M = 500;
vector adj[N];
int A[M], B[M];
int d[N], l[N], f[N];
int st[N], top, cnt;
int n, m;
void dfs(int u){
d[u] = l[u] = ++cnt;
st[top++] = u;
for (int i=0;i A[j]){
adj[2*i+1].push_back(2*j), adj[2*j].push_back(2*i+1);
adj[2*j+1].push_back(2*i), adj[2*i].push_back(2*j+1);
}
n = m;
}
void solve(){
memset(d, 0, sizeof(d));
cnt = top = 0;
for (int i=0;i<2*n;i++)
if (!d[i]) dfs(i);
}
bool check(){
for (int i=0;i
#include
#include
using namespace std;
const int N = 1000, M = 500;
int P[N], R[N]; // Ufs...
int A[M], B[M];
int n, m;
void Make(int x){
P[x] = x, R[x] = 0;
}
int Find(int x){
if (P[x] != x) P[x] = Find(P[x]);
return P[x];
}
void Union(int x, int y){
x = Find(x), y = Find(y);
if (R[x] < R[y]){
P[y] = x;
}
else {
P[x] = y;
if (R[x] == R[y]) R[y] ++ ;
}
}
void init(){
for (int i = 0; i < m; i ++){
scanf("%d%d", &A[i], &B[i]);
//if (B[i] < A[i]) swap(A[i], B[i]); //# 其實是完全不必要的吧。。。。。
}
for (int i = 0; i < m; i ++)
for (int j = i + 1; j < m; j ++)
if (A[j] < A[i]) swap(A[i], A[j]), swap(B[i], B[j]);
n = m;
}
void solve(){
for (int i = 0 ;i < 2*n; i ++)
Make(i);
for (int i = 0; i < n; i ++)
for (int j = i + 1; j < n; j ++)
if (B[i] < B[j] && B[i] > A[j])
Union(2*i, 2*j+1), Union(2*j, 2*i+1);
}
bool check(){
for (int i=0;i

### External link :