成绩排名: 初赛京津东北赛区82名
题意: 给定一个有向图,求出图中所有长度在[3,7]之间的环。
输入: 格式为[IDU,IDV,Weight]的边表,ID为32位无符号整数(当然题目说明了,小于2^31,所以int32就好),边最多28W条,不重复,结点平均度数小于10。环中同一个ID不可以重复出现(若大环包括小环,则需要分开统计),环的个数不大于300W。
输出: 环的个数,按照1.环长度;2.环的数字字典序输出所有环。
例子: 1,2,3的全连通图有两个符合题意的环
策略: dfs, 先正向遍历3层,再反向遍历3层标记节点。将搜索空间缩小,另外,最后一层的节点前驱做标记,遍历到第6个点时,提前做判定,不进入最后一层。6+1=7