[BUG] - missing solution in problem 1579 editorial

[sekerez]

LeetCode Username

sekerez

Problem Number, Title, and Link

1579. Remove Max Number of Edges to Keep Graph Fully Traversable https://leetcode.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/description/

Bug Category

Editorial

Bug Description

Not an actual bug, I just think that the editorial should include an additional solution which, while presenting a slightly worse complexity for the problem (O(n+e) instead of (O(e*ack(n))), still passes all testcases and I think is very simple! See my solution: https://leetcode.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/solutions/5398143/simple-linear-time-solution-no-union-find

Language Used for Code

Python/Python3

Code used for Submit/Run operation

ALICE, BOB, BOTH = 1, 2, 3

class Solution:
    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
        self.n = n
        self.connections = [[] for _ in range(self.n)]
        for t, u, v in edges:
            self.connections[u-1].append((t, v-1))
            self.connections[v-1].append((t, u-1))

        if not (self.is_traversible(ALICE) and self.is_traversible(BOB)):
            return -1

        num_type_3_edges_mst = self.count_type_3_mst_edges()

        return len(edges) + num_type_3_edges_mst - (n - 1) * 2

    def is_traversible(self, t: int) -> bool:
        visited = [False for _ in range(self.n)]
        self.dfs(visited, [t, BOTH], 0)
        return all(visited)

    def count_type_3_mst_edges(self) -> int:
        visited = [False for _ in range(self.n)]
        return sum(
            self.dfs(visited, [BOTH], node) 
            for node in range(self.n) if not visited[node]
        )

    def dfs(self, visited: list[bool], traversible_edges: list[int], node: int):
        visited[node] = True
        return sum(
            1 + self.dfs(visited, traversible_edges, v)
            for edge_type, v in self.connections[node]
            if not visited[v] and edge_type in traversible_edges
        )

Expected behavior

expect a second valid solution in the editorial, modeled after mine (basically, 3 dfs in a row)

Screenshots

No response

Additional context

No response

[exalate-issue-sync[bot]]

Epiphania_Ekenimoh commented: Hello,

Your reported issue has been relayed to our team for thorough investigation. We appreciate your patience as we work to address and resolve this matter. We will reach out to you when we have updates regarding the issue.

If you have any further questions or concerns in the meantime, please feel free to let us know.

Best regards, LeetCode Support Team

[exalate-issue-sync[bot]]

Epiphania_Ekenimoh commented: Hello there,

Thank you so much for your thoughtful feedback and for taking the time to share your solution!

We truly appreciate users like you who help improve the LeetCode experience for everyone. While your approach is indeed valuable, the current editorial solution is well-known and widely embraced by many users, thanks to its simplicity and effectiveness with the recurrent single approach. As a result, we won't be adding new solutions to this editorial at this time. However, your contribution is still greatly appreciated. Thank you again for your input!

Best, LeetCode Support Team