※ 引述《UesugiKura (上杉仓)》之铭言： : 在下今年要参加全国高职商科技艺竞赛 : 小的不才 其中有一道模拟试题一直不能想通怎麽去写 : 题目如下: : ---------------------------------------------------- : 写一个程式，读入一图形的资料，然後回答该图是否为树。 : 输入说明： : 第一列的数字n代表有几组资料要测试，而n的值介於1和10之间。 : 第二列以後则是每一组测试资料。每组测试资料代表一图形，内容为边的资料。 : 每个边以2个整数i,j表示，0<=i,j<=30，此2整数为节点的编号， : 代表从i节点和j节点有边相连。 : 0,0这个边代表此组输入资料结束。 : 输出说明： : 每组测试资料输出一列，输出每组测试资料以及该组测试资料是否为树。 : T为树，F不为树。（输出均为大写） : 输入档案1：【档名：in1.txt】 : 5 ...... : 3,8 6,8 6,4 5,3 5,6 8,2 2,0 0,0 树的规则你讲了一半，而重点是任二点之间「只有」一条路径. 一方面要找回路,另一方面要判断整个图是一个,没有切分成二部份. 如果找到是以上二种情况,就不是树. 前者,找回路,作法基本是像以下这样: 找5到6之间有没有回路,先从5开始建一个树, 第一层 第二层 第三层 5 - { 8, 4, 6 } - {{3,6,2}, 6, {8,4}} - 第四层 { {{5, {4,5}, 0}, {8,5}, {{3,2}, {}} } 每一层产生的原则,大概是看它上一层以及上上一层的关系,例如,第四层最後找到{}, 是由第三层的最右边节点4, "寻找与4相邻的节点,但扣掉4上一层节点6" 这样. 说是树,其实为了程式好做,是抄写成好几列: 5, 8, 3, 5, ... 5, 8, 6, 4, ... 5, 8, 6, 5, ... 5, 8, 2, 0, ... 5, 4, 6, 8, ... 5, 4, 6, 5, ... 5, 6, 8, 3, ... 5, 6, 8, 2, ... 5, 6, 4 每一列查过去,会发现 5,8,3,5,... 和 5,4,6,5,... 是回路. 至於第二个判断,判断任二点之间是否没有连通 (以决定图是否为一个完整单元), 不晓得是不是把图结构做出来,并在里头走访,看看如果全都走到尽头却碰不到目标, 则断定图型不是一个完整单元. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 118.167.50.25 ※ 编辑: yauhh 来自: 118.167.50.25 (11/27 01:00)