讨论/技术交流/求助|兄弟们,求解图论的一道题/
求助|兄弟们,求解图论的一道题

给定一个有向无权图,可能有环,每个顶点有一个蛋糕,一个小孩每次可以吃好几个蛋糕,但是对于不同的两个顶点 iijj,如果i可以到达 jj,那么就不能一次全部吃掉这两个顶点的蛋糕,问最少多少次可以吃完所有蛋糕?

比如结点数 n=5n = 5,边数 m=4m = 4
四条边是 1>21 -> 22>32 -> 33>13 -> 14>54 -> 5
那么需要三次。
因为 1,2,31,2,3 不能同时吃,4,54,5 也不能同时吃。

我用 DFSDFS 做的,但是超时了,想知道这道题怎么做?
谢谢各位大佬!

1

忘给样例了,
比如结点数n = 5,边数m = 4
四条边是1 -> 2, 2 -> 3, 3 -> 1, 4 -> 5
那么需要三次。
因为1,2,3不能同时吃,4,5也不能同时吃。

1
展开全部 6 讨论