题解

【HNOI2010】平面图判定

题目描述

若能将无向图 $G=(V, E)$ 画在平面上使得任意两条无重合顶点的边不相交,则称 $G$ 是平面图。判定一个图是否为平面图的问题是图论中的一个重要问题。现在假设你要判定的是一类特殊的图,图中存在一个包含所有顶点的环,即存在哈密顿回路。

题目链接

Luogu3209

题解

$\text{wjz}$ 布置的作业,我也觉得这道题很有意思,就顺手写一下题解了。
首先从特殊性质入手,图中有一条给定的哈密顿回路,就是说可以整一张图的所有点都可以被串成一个圈。
现在又有若干的边来连接圈上的点。如果两条边在圈内相连,那么就会冲突,就必须把一条边翻到圈外。但是不能把两条再圈内冲突的边都翻出去,因为都翻出去的话在圈外也会冲突。也就是说一条边要么是在圈内,要么是在圈外(环上的边显然无论如何不会冲突)。也就是说被分成了两个集合,并且有一些限制规定了某两条边不能在同一个集合中。
那么我们就把冲突的边新建一张图,新图的点是原图冲突的边,我们只需要判断新图的每一条边的两端是不是都可以不冲突地被划分到两个集合中。这显然是二分图,判断二分图就只需要二分图染色就可以了。
还有一个问题是,数据范围太大了,没法通过。
实际上这个数据范围是假的,根据平面图定理,有
$$m \leq 3 \times n – 6$$
这样就把 $m$ 降到了和 $n$ 一个数量级。如果不符合上面的式子就直接结束处理下一组数据,
时间复杂度 $O(tn^2)$

代码

#include <cmath>
#include <cstdio>
#include <cstring>
#include <climits>
#include <iostream>
#include <algorithm>
const int MAXM = 1e5 + 7;
struct Edge {
    int t, next;
} edge[MAXM << 1];
int head[MAXM], cnt;
int n, m;
int from[MAXM], to[MAXM], pos[MAXM];
int col[MAXM];
inline void add(int u, int v) {
    edge[++cnt] = (Edge){v, head[u]}; head[u] = cnt;
}
inline bool check(int u1, int v1, int u2, int v2) {
    return (u1 < u2 && u2 < v1 && v1 < v2) || (u2 < u1 && u1 < v2 && v2 < v1);
}
bool dfs(int u, int color) {
    col[u] = color;
    for (int e = head[u]; e; e = edge[e].next) {
        int v = edge[e].t;
        if (col[v] == color) return false;
        if (!col[v] && !dfs(v, 3 - color)) return false;
    }
    return true;
}
inline void init() {
    cnt = 0;
    memset(head, 0, sizeof head);
    memset(col, 0, sizeof col);
}
bool solve() {
    scanf("%d %d", &n, &m);
    init();
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", from + i, to + i);
    }
    int u;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &u);
        pos[u] = i;
    }
    if (m > 3 * n - 6) return false;
    for (int i = 1; i < m; i++) {
        for (int j = i + 1; j <= m; j++) {
            int u1 = pos[from[i]], v1 = pos[to[i]];
            int u2 = pos[from[j]], v2 = pos[to[j]];
            if (u1 > v1) std::swap(u1, v1);
            if (u2 > v2) std::swap(u2, v2);
            if (check(u1, v1, u2, v2)) add(i, j), add(j, i);
        }
    }
    for (int i = 1; i <= m; i++) {
        if (!col[i]) {
            if (!dfs(i, 1)) return false;
        }
    }
    return true;
}
int main(int argc, const char *argv[]) {
    int t;
    scanf("%d", &t);
    while (t--) {
        if (solve()) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

一条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注