【BZOJ1997】【HNOI2010】Planar

【タイトルリンク】

クリックしてリンク

を開く
【考え方のポイント】

のアーカイブブログで、問題はありません.

【コード】

#include
using namespace std;
#define MAXN	20005
int f[MAXN], x[MAXN], y[MAXN], home[MAXN], value[MAXN];
bool circle[MAXN];
int F(int x) {
	if (f[x] == x) return x;
	else return f[x] = F(f[x]);
}
int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		int n, m;
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= m; i++)
			scanf("%d%d", &x[i], &y[i]);
		for (int i = 1; i <= n; i++) {
			scanf("%d", &value[i]);
			home[value[i]] = i;
		}
		for (int i = 1; i <= m; i++) {
			x[i] = home[x[i]];
			y[i] = home[y[i]];
			if (x[i] > y[i]) swap(x[i], y[i]);
			if (x[i] + 1 == y[i] || (x[i] == 1 && y[i] == n)) circle[i] = true;
			else circle[i] = false;
		}
		if (m > 3 * n) {
			printf("NO
");
			continue;
		}
		for (int i = 1; i <= 2 * m + 1; i++)
			f[i] = i;
		for (int i = 1; i <= m; i++){
			if (circle[i]) continue;
			for (int j = i + 1; j <= m; j++) {
				if (circle[j]) continue;
				if (x[i] == x[j] || x[i] == y[j] || y[i] == x[j] || y[i] == y[j]) continue;
				if ((x[j] > x[i] && x[j] < y[i]) ^ (y[j] > x[i] && y[j] < y[i])) {
					int tmp = i * 2, tnp = j * 2;
					f[F(tmp)] = F(tnp ^ 1);
					f[F(tnp)] = F(tmp ^ 1);
				}
			}
		}
		bool flg = true;
		for (int i = 1; i <= m; i++)
			if (F(i * 2) == F(i * 2 ^ 1)) {
				flg = false;
				break;
			}
		if (flg) printf("YES
");
		else printf("NO
");
	}
	return 0;
}