题目描述

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

输入输出格式

输入格式:

输入文件的第一行是一个正整数T,表示数据组数(每组数据描述一个需要判定的图)。接下来从输入文件第二行开始有T组数据,每组数据的第一行是用空格隔开的两个正整数N和M,分别表示对应图的顶点数和边数。紧接着的M行,每行是用空格隔开的两个正整数u和v(1<=u,v<=n),表示对应图的一条边(u,v),输入的数据保证所有边仅出现一次。每组数据的最后一行是用空格隔开的N个正整数,从左到右表示对应图中的一个哈密顿回路:V1,V2,…,VN,即对任意i≠j有Vi≠Vj且对任意1<=i<=n-1有(Vi,Vi-1) ∈E及(V1,Vn) ∈E。输入的数据保证100%的数据满足T<=100,3<=N<=200,M<=10000。

输出格式:

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

输入输出样例

输入样例#1: 复制
输出样例#1: 复制

说明

感谢@hibiki 对题目进行修正

又是细节没注意

注意:先把哈密顿路径标记出来 然后其他边不是在他里面就是在他外面 注意判断一下即可 如果有端点重叠就认定肯定不会有冲突 然后每个点拆开 建限制条件跑2-sat即可

注意 如果边数大于点数的三倍-6那么就一定不会是平面图了

所以直接puts(”NO”) 但是因为多组数据所以得把这些没用的信息读进来..

 

分类: 2-SAT

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论