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 :
http://poj.org/problem?id=3207
                                                												

													Posted by 
													xiaodao													
													Category: 													POJ