[洛谷P3209]平面图判定题解

题目描述

背景
若能将无向图 $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,\cdots,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}$ ，注意均为大写字母