| 题目名称 | 2054. [ZOJ 1015]渔网 |
|---|---|
| 输入输出 | fishnet.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 8 |
| 题目来源 |
 mikumikumi
于2015-10-09加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：4， 提交：4， 通过率：100% | ||||
 Marvolo |
100 | 0.162 s | 4.21 MiB | C++ |
 甘罗 |
100 | 0.162 s | 4.21 MiB | C++ |
 葳棠殇 |
100 | 0.428 s | 4.18 MiB | C++ |
 mikumikumi |
100 | 0.530 s | 1.86 MiB | C++ |
| 关于 渔网 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
弦图 新技能Get √
葳棠殇
2016-03-26 18:07
2楼
| ||||
|
关于弦图的性质与算法请搜索陈丹琦的《弦图与区间图》
| ||||
【题目描述】
渔网的洞越小，捕到的鱼就越多。因此，渔民们在捕鱼回来后，都要检查一下渔网上有没有大的洞，以便在下次出海之前，将这些洞补好。
渔网被简单的看作一个由顶点和边构成的图。如果图中每一个长度大于3的圈，中间都至少有一段渔网（连接圈上两个顶点，且不在圈上的边）将其隔开，这个渔网就是完美的。请判断输入的渔网是否完美。
【输入格式】
多组数据，每组数据第一行是两个整数n，m（n<=1000),之后的m行，每行两个整数s，t，代表s，t之间有边相连
最后一行为0 0
【输出格式】
对于每组数据，判断渔网是否完美，如果完美，输出"Perfect",否则输出"Imperfect",每组输出间有换行
【样例输入】
4 4 1 2 2 3 3 4 4 1 3 3 1 2 2 3 3 1 0 0
【样例输出】
Imperfect Perfect
【提示】
在此键入。
【来源】
zoj1015