search

ChrisVilches / Algorithms

Solutions for competitive programming problems in various online judges such as Kattis, SPOJ, URI Online Judge, etc.
5 stars 0 forks source link

Exposing corruption may be bugged #3

Closed ChrisVilches closed 2 years ago

ChrisVilches commented 2 years ago

Increases component count even if the node has been visited (and does a DFS).

Maybe this assumption is incorrect. Check code.

ChrisVilches commented 2 years ago

Yes, it was incorrect. It created a new connected component object for every node even if it was already visited.

But since I had an array limit of 200 elements (the maximum possible, in the case where there are no edges at all), it never exceeded the array limits. Therefore the knapsack just had to deal with more objects, but the result is the same, since repeated objects don't impact the algorithm.

ChrisVilches commented 2 years ago

Code fixed: https://github.com/ChrisVilches/Algorithms/commit/bb53f59c287d248f4c672ab8ff06ccf0e9267e57