图算法解决方案做得对吗？

Question

我偶然发现了上一次Facebook黑客杯的问题(所以这不是我的作业,我觉得它非常有趣)而且我还想到了一个好奇但相当不错的解决方案.你能检查一下我的想法吗？这是任务:

您将获得一个拥有N个城市的网络和连接这些城市的M个双向道路.前K个城市很重要.您需要删除最少数量的道路,以便在剩余的网络中没有包含重要城市的周期.周期是至少三个不同城市的序列,使得每对相邻城市通过道路连接,并且序列中的第一个和最后一个城市也通过道路连接.

输入
第一行包含测试用例数T.

每个案例都以包含整数N,M和K的行开头,它们分别代表城市数量,道路数量和重要城市数量.城市编号从0到N-1,重要城市编号从0到K-1.以下M行包含两个整数a [i]和b [i],0≤i<M,表示由道路连接的两个不同城市.

保证0≤a[i],b [i] <N且a [i]≠b [i].两个城市之间最多只有一条道路.

输出
对于按从1到T的顺序编号的每个测试用例,输出"Case #i:"后跟一个整数,需要删除的最小道路数,使得没有包含重要城市的周期.

约束
1≤:T≤20
1≤N≤10000
1≤中号≤50000
1≤ķ≤Ñ

示例
在第一个示例中,我们有N = 5个城市,这些城市通过M = 7条道路连接,城市0和1是重要的.我们可以删除连接(0,1)和(1,2)的两条道路,其余网络不包含重要城市的周期.请注意,在剩余的网络中,有一个仅包含非重要城市的循环,并且还有多种方法可以移除两条道路并满足所有条件.人们不能只移除一条道路并摧毁包含重要城市的所有周期.

输入示例
1
5 7 2
0 1
1 2
1 4
0 2
2 4
2 3
3 4

所以我这样想:在构建图形时,让我们有一个单独的数组,存储每个城市有多少邻居的信息(= =有多少条道路连接到给定城市).在示例中,城市0有2,城市1有3,依此类推.让我们称这个数字为特定城市的"城市价值".

在获得整个输入之后,我们通过整个城市值来寻找具有值1的城市.当达到一个时,这意味着它不能处于循环中,因此我们减少其值"删除"(没有损失)一般性的)将它连接到它的唯一邻居并减少邻居价值的道路.在那之后,我们递归地去邻居检查相同的事情,如果值为1那么 - 重复该方案并递归地更深入.如果不是 - 请勿触摸.

在那个操作之后,我们已经清除了图形中不是周期的所有部分,并且不能成为图形的一部分.我们也摆脱了所有没有任何意义的道路.所以我们称之为另一个功能,这次 - 仅在重要城市工作.因此我们采用顶点1 - 在使用前一段中描述的函数之后,其值不能为1(因为它已经被函数设为零)所以它是0或者等于> 1.在第一种情况下,我们不必做任何事情.在后者中,我们必须通过执行值-1删除来创建值1.与前一段类似,在每次移除后,我们减少这个城市及其邻居的价值,同时删除道路.我们重复所有k个重要城市,从所有重要城市总结价值-1,这就是我们的答案.

它有意义吗？对于我尝试过的所有测试,我想相信它是正确的但我觉得某处可能存在泄漏.你能检查一下吗？这有什么好处吗？如果没有,为什么和这个思想过程有什么关系？:)

Answer 1

这是一个错误的解决方案。

您的解决方案的反例。假设正方形中的那一个是唯一重要的。您的解决方案将删除一条道路。