题意

判断一个存在哈密顿回路的图是否是平面图。

n≤200,m≤10000n\le200,m\le10000n≤200,m≤10000

题解

如果一定存在一个环，那么连的边要么在环里面要么在外面。那么把在同侧会矛盾的边之间连边，如果是一个二分图就是平面图。

有问题的是边数是O(m2)O(m^2)O(m2)的。但是可以发现当m>n∗3−6m>n*3-6m>n∗3−6的时候一定形成不了平面图。所以就判一下，如果小于等于就O(m2)O(m^2)O(m2)做。

证明：先画出一条环，有nnn条边，然后这个环的一个点向非相邻的n−3n-3n−3个点连接n−3n-3n−3条边可以保证两两不相交，外面一侧如此，故如果边数m>n∗3−6m>n*3-6m>n∗3−6，就直接判断NONONO即可。保证了复杂度。

判二分图的方法可以用带权并查集或者直接染色，这里写的是带权并查集。

CODE

#include <bits/stdc++.h>

using namespace std;

inline void rd(int &x) {

	char ch; for(;!isdigit(ch=getchar()););

	for(x=ch-'0';isdigit(ch=getchar());)x=x*10+ch-'0';

}

const int MAXN = 205;

const int MAXM = 10005;

int n, m, u[MAXM], v[MAXM], seq[MAXN], id[MAXN];

int d[MAXM], fa[MAXM];

int find(int x) {

	if(x != fa[x]) {

		int old = fa[x];

		fa[x] = find(fa[x]);

		d[x] ^= d[old];

	}

	return fa[x];

}

int main() {

	int T; rd(T); while(T--) {

		rd(n), rd(m);

		for(int i = 1; i <= m; ++i) rd(u[i]), rd(v[i]);

		for(int i = 1; i <= n; ++i) rd(seq[i]), id[seq[i]] = i;

		if(m > 3*n-6) puts("NO");

		else {

			bool flg = 1;

			for(int i = 1; i <= m && flg; ++i) {

				fa[i] = i; d[i] = 0;

				int l = min(id[u[i]], id[v[i]]);

				int r = max(id[u[i]], id[v[i]]);

				for(int j = 1; j < i && flg; ++j)

					if(id[u[j]] != l && id[u[j]] != r && id[v[j]] != l && id[v[j]] != r && ((l <= id[u[j]] && id[u[j]] <= r)^(l <= id[v[j]] && id[v[j]] <= r))) {

						int u = find(i), v = find(j);

						if(u == v) flg &= (d[i] != d[j]);

						else fa[u] = v, d[u] = d[i] ^ d[j] ^ 1;

					}

			}

			puts(flg ? "YES" : "NO");

		}

	}

}

巴特西

BZOJ1997 HNOI2010 平面图判定 planar （并查集判二分图）

题意

题解

CODE

最新文章

热门文章