C++ | kruskal algorithm | easy to follow code
Try to include Type 3 edges maximally (1.set)\n2. Count number of type1 edges that we can add to 1.set with out introducing any cycle.\n3. Count number of type2
1. Try to include Type 3 edges maximally (1.set)\n2. Count number of type1 edges that we can add to 1.set with out introducing any cycle.\n3. Count number of type2 edges that we can add to 1.set with out introducing any cycle.\n\nthe answer will be (totoal_#_edges - size_of_set.1 - #_2 - #_3)\n\n```\nclass Solution {\npublic:\n    vector<pair<long long, pair<int, int>>> p;\n    vector<int> id;\n    int N;\n\n    void initialize() {\n        id.resize(N);\n        p.resize(N);\n        for(int i = 0;i < N;++i)\n            id[i] = i;\n    }\n\n    int root(int x) {\n        while(id[x] != x) {\n            id[x] = id[id[x]];\n            x = id[x];\n        }\n\n        return x;\n    }\n\n    void union1(int x, int y) {\n        int p = root(x);\n        int q = root(y);\n        id[p] = id[q];\n    }\n\n    int check_type(int type, int n, vector<vector<int>>& edges) {\n        int x, y;\n        int min_c = 0;\n        for(int i = 0;i < edges.size();i++) {\n            int x=edges[i][1];\n            int y=edges[i][2];\n            if (edges[i][0] == type && root(x) != root(y)) {\n                min_c++;\n                union1(x, y);\n            }\n        }\n        \n        return min_c;\n    }\n\n    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {\n        N=n+1;\n        initialize();\n        int t3 = check_type(3, n, edges);\n        auto p_temp = p;\n        auto id_temp = id;\n        int t1 = check_type(1, n, edges);\n        p=p_temp;\n        id=id_temp;\n        int t2 = check_type(2, n, edges);\n\n        if (t3+t1 != n - 1 || t3+t2 != n - 1) {\n            return -1;\n        }\n        \n        return edges.size()-t3-t1-t2;\n    }\n};\n```
['Union Find', 'C']