P3209 [HNOI2010]平面图判定

    • 516通过
    • 1.9K提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 2-SAT 二分图 并查集 2010 湖南 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

    输入输出格式

    输入格式:

    输入文件的第一行是一个正整数 $T$,表示数据组数 (每组数据描述一个需要判定的图)。接下来从输入文件第二行开始有 $T$ 组数据,每组数据的第一行是用空格隔开的两个正整数 $N$ 和 $M$,分别表示对应图的顶点数和边数。紧接着的 $M$ 行,每行是用空格隔开的两个正整数 $u$ 和 $v$ $\left(1\leq u,v\leq N\right)$,表示对应图的一条边 $\left(u,v\right)$, 输入的数据保证所有边仅出现一次。每组数据的最后一行是用空格隔开的 $N$ 个正整数,从左到右表示对应图中的一个哈密顿回路:$V_1,V_2,…,V_N$,即对任意 $i\not=j$ 有 $V_i\not=V_j$ 且对任意 $1\leq i\leq N-1$ 有 $\left(V_i,V_i-1\right)\in E$ 及 $\left(V_1,V_N\right)\in E$。输入的数据保证 $100\%$ 的数据满足 $T\leq100,3\leq N\leq200,M\leq10000$。

    输出格式:

    包含 $T$ 行,若输入文件的第 $i$ 组数据所对应图是平面图,则在第 $i$ 行输出 $\text{YES}$,否则在第 $i$ 行输出 $\text{NO}$,注意均为大写字母

    输入输出样例

    输入样例#1: 复制
    2
    6 9
    1 4
    1 5
    1 6
    2 4
    2 5
    2 6
    3 4
    3 5
    3 6
    1 4 2 5 3 6
    5 5
    1 2
    2 3
    3 4
    4 5
    5 1
    1 2 3 4 5
    输出样例#1: 复制
    NO
    YES

    说明

    感谢@hibiki 对题目进行修正

    感谢@@Anguei 提供latex题面

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。