文件名称:leetcode双人赛-Algorithm:算法
文件大小:828KB
文件格式:ZIP
更新时间:2024-07-19 22:45:59
系统开源
leetcode双人赛 Algorithm This is the algorithm exercise for my interview, come on!! ##深度优先搜索 ####dfs_codeforce_659E_New_Reform 题意:有n座城市,城市之间有无向边,现在要把所有的边变成有向的边,使得入度为0的城市尽可能的少。 解答:如果是无向边构成的图,可以看成是一颗“树”,正常情况下的树只有根节点入度是0.但是,如果原来的图有环,所有的节点的入度都可以不为0,只要循环指向即可。因此,问题转化为dfs找环。遍历所有的联通集合,如果有环,则这个集合可以不存在入度为0的节点,否则,总结果+1. ###如何求树的直径??树中距离最大的两个点 解答:对于任意一个节点,用bfs求到它最远的点s,则这个点s必是直径的一个点。在从s出发,bfs找到另一个最远的点t,(s,t)就是直径。 ##动态规划: ###普通dp ####hdu_4248_A_Famous_Stone_Collector 题意:给n堆不同颜色的石头,给定每堆石子的数量,问,能够组成多少串满足:Two patte