/ Vijos / 题库 /

小胖的难题

小胖的难题

描述

王小胖最近对图论产生了很浓的兴趣,尤其是关于回路的问题。

回路是图论中经典的内容。回路相关知识定义如下:
通路的长度:通路中边的条数。
回路:如果通路中始点与终点相同。
简单通路:如果通路中各边都不相同。

基本通路:如果通路中各顶点都不相同。显然(基本通路一定是简单通路,但简单通路不一定是基本通路)
简单回路:如果一个回路中任意两点都是简单通路。

可达:在图G中如果存在一条v到d通路则称从v到d是可达。
连通:在无向图中如果任意两点是可达的,否则是不连通的。

王小胖因此用了很长一段时间研究了回路。以下是王小胖的研究成果。首先王小胖给出了欧拉回路的定义:
(给定无孤立点图G,若存在一条路,经过图中每边一次且仅一次,该条路称为欧拉路;若存在一条回路,经过图中的每边一次且仅一次,该回路称为欧拉回路)
然后王小胖又给出了哈密尔顿回路的定义:
(给定图G,若存在一条回路,经过图中的每一个结点恰好一次,这个回路称作汉密尔顿回路)
王小胖是一个善于思考的小胖,他显然不会满足于这些知识,于是他发明了一种”小胖回路”,小胖回路定义如下:
(给定图G,若存在一条简单回路Vi1,Vi2,Vi3…Vik 其中Vi1=Vik ,如果k是奇数,那么这个回路称作小胖回路)
现在王小胖想考考你对于回路的认识,所以这个任务由你来完成。你的任务如下,给定一个N(N<=800)个点,M条边(M<=40000)的无向图。每次删去一个点,与这个点相连的边随之消失,询问是否有小胖回路,共删除P次(P<=N/2),每次删除后如果有输出”The Graph has Fat Tour.”,否则输出”Poor Fat Tour.”。

格式

输入格式

包含1+M+P行。第一行3个正整数,从左至右依次给出N,M,P。

第2到M+1行,每行两个整数x,y。(1<=x,y<=N,x<>y)
第M+2到M+P+1行,每行一个整数,删除编号为Pi的结点。

输出格式

包含P行,每行一句话,说明是否存在小胖回路。

样例1

样例输入1

4 4 1
1 2
2 3
3 1
3 4
4

样例输出1

The Graph has Fat Tour.

限制

各个测试点2s

信息

ID
1462
难度
6
分类
图结构 | 二分图 点击显示
标签
(无)
递交数
257
已通过
72
通过率
28%
被复制
2
上传者

相关

在下列训练计划中:

RP++分类题库