主题

主题

 
   

1997: [Hnoi2010]Planar

原题:https://www.luogu.org/problem/show?pid=3209/http://www.lydsy.com/JudgeOnline/problem.php?id=1997

题目描述

若能将无向图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:

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


个人解法:

把哈密顿回路拿出来当成一个环。之后其他边可能在环内,也可能在环外。

变得与POJ某题一模一样……

然后发现边数极高。

看到PoPoQQQ大爷,以及Hzwer大爷的博客,都说如果m>3n-6,就不可能是平面图了。

然后去找了一下网上的文库,好像是一个推论……

反正平面图知识为0……


代码如下:

https://code.csdn.net/snippets/2294915


为什么2-sat+Tarjan与并查集的差距这么大?

 
 
评论