# 某岛

… : "…アッカリ～ン . .. . " .. .
March 25, 2011

## POJ 3207. Ikki’s Story IV – Panda’s Trick

### Analyse :

。。。是可以用并查集直接写的吧。。

#include
#include
using namespace std;

const int INF = 0x7fffffff;
const int N = 1000, M = 500;
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]){
}
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