✍ ✅ [PHP][JavaScript] 🚀Beats 100% | Using Union Find or Disjoint-set data structure
This approach uses UnionFind to determine the number of edges to remove in order to disconnect a graph with edges of type 1, 2, and 3. \n\nThe union-find data s
This approach uses UnionFind to determine the number of edges to remove in order to disconnect a graph with edges of type 1, 2, and 3. \n\nThe union-find data structure helps to keep track of connected components in the graph. \n\nThe algorithm first iterates over all the edges of type 3 and uses the union-find data structure to union all the nodes connected by these edges. \nIt then iterates over the edges of type 1 and 2 for each one, it checks if the two nodes connected by this edge have been already connected (using union-find) or not. \nIf they are not connected, then the edge is added (using union-find) and the number of edges to keep is incremented. \n\nFinally, the algorithm checks if the graph is connected *isConnected* and if it is, it return the number of edges that need to be removed *(edges.length - resNumberOfEdgesToKeep)*, else it returns -1.\n\n# Complexity\n- Time complexity: $$O(m * log(n))$$ where *m* is the number of edges and *n* is the number of nodes. \n- Space complexity: $$O(N)$$, where N is the number of vertices.\n\n# JavaScript\n``` JavaScript\n/**\n * @param {number} n\n * @param {number[][]} edges\n * @return {number}\n */\nvar maxNumEdgesToRemove = function (n, edges) {\n    let ufA = new UnionFind(n);\n    let ufB = new UnionFind(n);\n    let resNumberOfEdgesToKeep = 0;\n    // Type 3\n    for (let edge of edges) {\n        if (edge[0] === 3) {\n            resNumberOfEdgesToKeep += ufA.union(edge[1], edge[2]);\n            ufB.union(edge[1], edge[2]);\n        }\n    }\n    // Type 1 and 2\n    for (let edge of edges) {\n        if (edge[0] === 1) {\n            resNumberOfEdgesToKeep += ufA.union(edge[1], edge[2]);\n        } else if (edge[0] === 2) {\n            resNumberOfEdgesToKeep += ufB.union(edge[1], edge[2]);\n        }\n    }\n    return ufA.isConnected() && ufB.isConnected() ? edges.length - resNumberOfEdgesToKeep : -1;\n};\n\nclass UnionFind {\n    constructor(n) {\n        this.parent = {};\n        this.rank = {};\n        this.count = n;\n        for (let i = 0; i <= n; i++) {\n            this.parent[i] = i;\n            this.rank[i] = 1;\n        }\n    }\n\n    find(node) {\n        while (node !== this.parent[node]) {\n            this.parent[node] = this.parent[this.parent[node]];\n            node = this.parent[node];\n        }\n        return node;\n    }\n\n    union(u, v) {\n        let rootU = this.find(u);\n        let rootV = this.find(v);\n        if (rootU === rootV) return 0;\n        if (this.rank[rootU] > this.rank[rootV]) {\n            this.parent[rootV] = rootU;\n            this.rank[rootU] += this.rank[rootV];\n        } else {\n            this.parent[rootU] = rootV;\n            this.rank[rootV] += this.rank[rootU];\n        }\n        this.count--;\n        return 1;\n    }\n\n    isConnected() {\n        return this.count === 1;\n    }\n}\n```\n\n# PHP\n``` PHP\nclass Solution\n{\n    /**\n     * @param Integer $n\n     * @param Integer[][] $edges\n     * @return Integer\n     */\n    function maxNumEdgesToRemove(int $n, array $edges): int {\n        $ufA = new UnionFind($n);\n        $ufB = new UnionFind($n);\n        $resNumberOfEdgesToKeep = 0;\n        // Type 3\n        foreach ($edges as $edge) {\n            if ($edge[0] == 3) {\n                $resNumberOfEdgesToKeep += $ufA->union($edge[1], $edge[2]);\n                $ufB->union($edge[1], $edge[2]);\n            }\n        }\n        // Type 1 and 2\n        foreach ($edges as $edge) {\n            if ($edge[0] == 1) {\n                $resNumberOfEdgesToKeep += $ufA->union($edge[1], $edge[2]);\n            } else if ($edge[0] == 2) {\n                $resNumberOfEdgesToKeep += $ufB->union($edge[1], $edge[2]);\n            }\n        }\n        return $ufA->isConnected() && $ufB->isConnected() ? count($edges) - $resNumberOfEdgesToKeep : -1;\n    }\n}\n\nclass UnionFind\n{\n    private $parent = [];\n    private $rank = [];\n    private $count = 0;\n\n    function __construct(int $n) {\n        $this->count = $n;\n        for ($i = 0; $i <= $n; $i++) {\n            $this->parent[$i] = $i;\n            $this->rank[$i] = 1;\n        }\n    }\n\n    function find(int $node): int {\n        while ($node != $this->parent[$node]) {\n            $this->parent[$node] = $this->parent[$this->parent[$node]];\n            $node = $this->parent[$node];\n        }\n        return $node;\n    }\n\n    function union(int $u, int $v): int {\n        $rootU = $this->find($u);\n        $rootV = $this->find($v);\n        if ($rootU == $rootV) return 0;\n        if ($this->rank[$rootU] > $this->rank[$rootV]) {\n            $this->parent[$rootV] = $rootU;\n            $this->rank[$rootU] += $this->rank[$rootV];\n        } else {\n            $this->parent[$rootU] = $rootV;\n            $this->rank[$rootV] += $this->rank[$rootU];\n        }\n        $this->count--;\n        return 1;\n    }\n\n    function isConnected(): bool {\n        return $this->count == 1;\n    }\n}\n```\n\n\n##### Thanks for reading! If you have any questions or suggestions, please leave a comment below. I would love to hear your thoughts! \uD83D\uDE0A\n### **Please upvote if you found this post helpful! \uD83D\uDC4D**
['Union Find', 'Graph', 'PHP', 'JavaScript']