PAT 解题报告 1021. Deepest Root (25)

题目描述:

给出一个图(不一定是一颗树), 要你选出图的某个节点, 使得以这个节点为根的树最深. 这样的节点可能存在多个, 也有可能本身这个图不是一颗树, 不是树的情况要求输出k-components, k是这个图的联通component的个数.

算法分析:

对给定的图的每一个node, 进行一次DFS, 找到以这个node为根的树深度, 并且标记所以和这个node联通的node. 完了以后, 我们就可以得到以每个node为根的树的深度, 以及每个node所在的联通component, 要是只有一个componet那么按照要求输出最深的根node, 不然就输出error和联通数量.

注意点:

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on July 12, 2013