LeetCode 1579: Remove Max Number of Edges to Keep Graph Fully Traversable Solution

Master LeetCode problem 1579 (Remove Max Number of Edges to Keep Graph Fully Traversable), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1579. Remove Max Number of Edges to Keep Graph Fully Traversable

Hard

Union Find Graph

Problem Explanation

Explanation:

We need to find the maximum number of edges we can remove so that the graph can still be fully traversed by both Alice and Bob.
We can achieve this by simulating the process of building the graph by Alice and Bob separately and counting the number of edges that can be removed without affecting the full traversal by both.
We will use Disjoint Set Union (DSU) data structure to keep track of the connected components for Alice and Bob separately.
We will iterate through the edges and process type 3 edges first, then process type 1 and type 2 edges separately for Alice and Bob.
If at any point both Alice and Bob can reach all nodes, we can remove that edge. If Alice or Bob cannot reach all nodes, we can't remove that edge.
Finally, we return the maximum number of edges that can be removed.

Solution Code

class Solution {
    public int maxNumEdgesToRemove(int n, int[][] edges) {
        DSU alice = new DSU(n);
        DSU bob = new DSU(n);
        int removedEdges = 0;

        // Process Type 3 edges
        for (int[] edge : edges) {
            if (edge[0] == 3) {
                if (!alice.union(edge[1], edge[2]) || !bob.union(edge[1], edge[2])) {
                    removedEdges++;
                }
            }
        }

        // Process Type 1 edges for Alice
        for (int[] edge : edges) {
            if (edge[0] == 1) {
                if (!alice.union(edge[1], edge[2])) {
                    removedEdges++;
                }
            }
        }

        // Process Type 2 edges for Bob
        for (int[] edge : edges) {
            if (edge[0] == 2) {
                if (!bob.union(edge[1], edge[2])) {
                    removedEdges++;
                }
            }
        }

        return alice.isConnected() && bob.isConnected() ? removedEdges : -1;
    }

    class DSU {
        int[] parent;

        public DSU(int n) {
            parent = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public boolean union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return false;
            }
            parent[rootX] = rootY;
            return true;
        }

        public boolean isConnected() {
            int root = find(1);
            for (int i = 2; i < parent.length; i++) {
                if (find(i) != root) {
                    return false;
                }
            }
            return true;
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1579 (Remove Max Number of Edges to Keep Graph Fully Traversable)?

This page provides optimized solutions for LeetCode problem 1579 (Remove Max Number of Edges to Keep Graph Fully Traversable) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1579 (Remove Max Number of Edges to Keep Graph Fully Traversable)?

The time complexity for LeetCode 1579 (Remove Max Number of Edges to Keep Graph Fully Traversable) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1579 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1579 in Java, C++, or Python.

Back to LeetCode Solutions