C++ Kruskal's algorithm||Beats 95.26%||Math
Intuition\n Describe your first thoughts on how to solve this problem. \nIt is Graph Theory Problem for Master\'s Degree Study. Krusal\'s algorithm in short:\n\
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIt is Graph Theory Problem for Master\'s Degree Study. Krusal\'s algorithm in short:\n```\n        for(int i=0; i<e; i++){// in ascending order w.r.t weights\n            auto& edge=edges[i];\n            int d=edge[0], v=edge[2], w=edge[3];\n            if (i==removal || i==inclusive) continue;\n            if (uf.Find(v) == uf.Find(w)) continue;\n            uf.Union(v, w);\n            dist+=d;//sum for weights\n        }\n```\n# Approach\n<!-- Describe your approach to solving the problem. -->\nUse Kruskal\'s algorithm based on Union Find.\n1. Sort the edges with indexes i\'s w.r.t. weight\n2. Compute the weight for MST by using Kruskal\'s algorithm\n3. Use Kruskal\'s Algorithm to compute the minimal weighted spanning tree according to edges[i] exclusive or inclusive. With this info one can find  the critical edges and pseudo-critical edges\n\nLet\'s consider the test case\n```\n14\n[[0,1,13],[0,2,6],[2,3,13],[3,4,4],[0,5,11],[4,6,14],[4,7,8],[2,8,6],[4,9,6],[7,10,4],[5,11,3],[6,12,7],[12,13,9],[7,13,2],[5,13,10],[0,6,4],[2,7,3],[0,7,8],[1,12,9],[10,12,11],[1,2,7],[1,3,10],[3,10,6],[6,10,4],[4,8,5],[1,13,4],[11,13,8],[2,12,10],[5,8,1],[3,7,6],[7,12,12],[1,7,9],[5,9,1],[2,13,10],[10,11,4],[3,5,10],[6,11,14],[5,12,3],[0,8,13],[8,9,1],[3,6,8],[0,3,4],[2,9,6],[0,11,4],[2,5,14],[4,11,2],[7,11,11],[1,11,6],[2,10,12],[0,13,4],[3,9,9],[4,12,3],[6,7,10],[6,8,13],[9,11,3],[1,6,2],[2,4,12],[0,10,3],[3,12,1],[3,8,12],[1,8,6],[8,13,2],[10,13,12],[9,13,11],[2,11,14],[5,10,9],[5,6,10],[2,6,9],[4,10,7],[3,13,10],[4,13,3],[3,11,9],[7,9,14],[6,9,5],[1,5,12],[4,5,3],[11,12,3],[0,4,8],[5,7,8],[9,12,13],[8,12,12],[1,10,6],[1,9,9],[7,8,9],[9,10,13],[8,11,3],[6,13,7],[0,12,10],[1,4,8],[8,10,2]]\n```\nUse Kruskal\'s Algorithm to compute the minimal weighted spanning tree according to edges[i] exclusive or inclusive as follows\n```\nminimal weight=29\n28-> excl:29 incl:29\n32-> excl:29 incl:29\n39-> excl:29 incl:29\n58-> excl:32 incl:29\n13-> excl:31 incl:29\n45-> excl:30 incl:29\n55-> excl:31 incl:29\n61-> excl:30 incl:29\n89-> excl:31 incl:29\n10-> excl:29 incl:29\n16-> excl:32 incl:29\n37-> excl:29 incl:29\n51-> excl:29 incl:29\n54-> excl:29 incl:29\n57-> excl:30 incl:29\n70-> excl:29 incl:29\n75-> excl:29 incl:29\n76-> excl:29 incl:29\n85-> excl:29 incl:29\n3-> excl:29 incl:30\n9-> excl:29 incl:31\n15-> excl:29 incl:29\n23-> excl:29 incl:29\n25-> excl:29 incl:29\n34-> excl:29 incl:30\n41-> excl:29 incl:30\n43-> excl:29 incl:30\n49-> excl:29 incl:30\n24-> excl:29 incl:31\n73-> excl:29 incl:30\n1-> excl:29 incl:32\n7-> excl:29 incl:32\n8-> excl:29 incl:32\n22-> excl:29 incl:32\n29-> excl:29 incl:32\n42-> excl:29 incl:32\n47-> excl:29 incl:31\n60-> excl:29 incl:31\n81-> excl:29 incl:31\n11-> excl:29 incl:32\n20-> excl:29 incl:32\n68-> excl:29 incl:33\n86-> excl:29 incl:32\n6-> excl:29 incl:34\n17-> excl:29 incl:34\n26-> excl:29 incl:34\n40-> excl:29 incl:33\n77-> excl:29 incl:34\n78-> excl:29 incl:35\n88-> excl:29 incl:33\n12-> excl:29 incl:35\n18-> excl:29 incl:34\n31-> excl:29 incl:34\n50-> excl:29 incl:35\n65-> excl:29 incl:36\n67-> excl:29 incl:34\n71-> excl:29 incl:35\n82-> excl:29 incl:34\n83-> excl:29 incl:36\n14-> excl:29 incl:37\n21-> excl:29 incl:35\n27-> excl:29 incl:36\n33-> excl:29 incl:36\n35-> excl:29 incl:36\n52-> excl:29 incl:35\n66-> excl:29 incl:35\n69-> excl:29 incl:36\n87-> excl:29 incl:36\n4-> excl:29 incl:37\n19-> excl:29 incl:37\n46-> excl:29 incl:37\n63-> excl:29 incl:38\n30-> excl:29 incl:38\n48-> excl:29 incl:38\n56-> excl:29 incl:38\n59-> excl:29 incl:38\n62-> excl:29 incl:39\n74-> excl:29 incl:37\n80-> excl:29 incl:38\n0-> excl:29 incl:38\n2-> excl:29 incl:39\n38-> excl:29 incl:39\n53-> excl:29 incl:38\n79-> excl:29 incl:39\n84-> excl:29 incl:40\n5-> excl:29 incl:39\n36-> excl:29 incl:39\n44-> excl:29 incl:40\n64-> excl:29 incl:40\n72-> excl:29 incl:41\n```\nIt\'s possible to modify the code with some Optimizations by reducing the times of applying Kruskal\'s algorithm. Both of critical edges and pseudo-critical edges have the following relation with  minimal spanning trees:\n# Proposition 1\n$$\n\\{Critical\\}\\subset \\bigcap MST \n$$\nProof. Suppose there were some critical edge e which is not contained in in some MST T. But due to the definition for a critical edge "An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge" The cost of T is the same as other MST. A contradiction! Q.E.D.\n# Proposition 2\n$$\n\\{Pseudo Critical \\}\\subset \\bigcup MST \\setminus \\bigcap MST \n$$\nProof. Just the definition" a pseudo-critical edge is that which can appear in some MSTs but not all." Q.E.D.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n//Kruskal\'s algorithm\nclass UnionFind {    \n    vector<int> root, rank;\npublic:\n    UnionFind(int n) : root(n), rank(n) {\n        rank.assign(n, 1);\n        for (int i = 0; i <n; i++) \n            root[i] = i;\n    }\n\n    int Find(int x) {\n        if (x == root[x]) return x;\n        else return root[x] = Find(root[x]);\n    }\n\n    void Union(int x, int y) {\n        int rX = Find(x), rY = Find(y);\n        if (rX == rY)  return;\n        if (rank[rX] > rank[rY]) swap(rX, rY);   \n        root[rX] = rY;\n        if (rank[rX]==rank[rY]) rank[rY]++;\n    }\n\n    bool connected(int x, int y) {\n        return Find(x) == Find(y);\n    }\n\n};\nclass Solution {\npublic:\n    int e;\n    int Kruskal(int n, vector<vector<int>>& edges, int removal=-1, int inclusive=-1)   \n    {\n        UnionFind uf(n);\n        int dist=0;\n        if (inclusive!=-1){\n            auto& edge=edges[inclusive];\n            int d=edge[0], v=edge[2], w=edge[3];\n            uf.Union(v, w);\n            dist+=d;\n        }\n        for(int i=0; i<e; i++){\n            auto& edge=edges[i];\n            int d=edge[0], v=edge[2], w=edge[3];\n            if (i==removal || i==inclusive) continue;\n            if (uf.Find(v) == uf.Find(w)) continue;\n            uf.Union(v, w);\n            dist+=d;\n        }\n        for(int i=1; i<n; i++)\n            if (!uf.connected(0, i)) return INT_MAX;//disconnected\n        return dist;\n    }\n\n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) \n    {\n        e=edges.size();\n        for(int i=0; i<e; i++){\n            vector<int>& edge=edges[i];\n            vector<int> e2={edge[2], i, edge[0], edge[1]};\n            edge=e2;\n        }\n        sort(edges.begin(), edges.end());\n    //    for(auto& ee: edges)\n    //        cout<<ee[0]<<","<<ee[1]<<","<<ee[2]<<","<<ee[3]<<endl;\n\n        int minWeight= Kruskal(n, edges);\n        cout<<minWeight<<endl;\n   \n        vector<int> critical, pseudo_crt;\n        \n        for(int j=0; j<e; j++){ \n            int i=edges[j][1];\n            int no_j=Kruskal(n, edges, j), w_j=Kruskal(n, edges, -1, j);\n        //    cout<<i<<"-> wo:"<<no_j<<" with:"<<w_j<<endl;  \n            if(minWeight<no_j)\n                critical.push_back(i);\n            else if (minWeight==w_j)\n                pseudo_crt.push_back(i);\n        }\n        return {critical, pseudo_crt};\n    }\n};\n```\n# Code with some Optimizations by reducing the times of applying Kruskal\'s algorithm Beats 95.26%\n\n```\n//Kruskal\'s algorithm\nclass Solution {\npublic:\n    int e;\n    vector<bool> i_edge;\n    int Kruskal(int n, vector<vector<int>>& edges,  \n    vector<int>& MST, //edges for Minimal spanning Tree\n    int removal=-1, int inclusive=-1)   \n    {\n        UnionFind uf(n);\n        int dist=0;\n        int edges_choosen=0;\n        if (inclusive!=-1){\n            auto& edge=edges[inclusive];\n            int d=edge[0], index=edge[1], v=edge[2], w=edge[3];\n            uf.Union(v, w);\n            edges_choosen++;\n            dist+=d;\n            MST.push_back(inclusive);\n        }\n        \n        for(int i=0; i<e; i++){\n            auto& edge=edges[i];\n            int d=edge[0], index=edge[1], v=edge[2], w=edge[3];\n            if (i==removal || i==inclusive) continue;\n            if (uf.Find(v) == uf.Find(w)) continue;\n            uf.Union(v, w);\n            edges_choosen++;\n            dist+=d;\n            MST.push_back(i);\n        }\n        if (edges_choosen!=n-1) return INT_MAX;//disconnected\n        return dist;\n    }\n\n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) \n    {\n        e=edges.size();\n        for(int i=0; i<e; i++){\n            vector<int>& edge=edges[i];\n            vector<int> e2={edge[2], i, edge[0], edge[1]};\n            edge=e2;\n        }\n        sort(edges.begin(), edges.end());\n    \n        vector<int> MST;\n        int minWeight=Kruskal(n, edges, MST);\n\n        vector<int> critical, pseudo_crt;\n        vector<bool> ctl(e,0);//bool tables for indexs Critical edges\n        vector<bool> ctl_ps(e,0);// tables for indexes for ctl/ps_ctl edges\n    //    cout<<"eMST=[";\n        for(int j: MST){\n            int i=edges[j][1];\n            vector<int> mst;\n            int no_j=Kruskal(n, edges, mst, j, -1);\n            if(minWeight<no_j){\n                critical.push_back(i);\n                ctl[i]=1;\n            }\n            else if (minWeight==no_j){\n                for(int k: mst)\n                    ctl_ps[edges[k][1]]=1;\n            }     \n    //        cout<<i<<",";\n        }     \n    //    cout<<"]\\n";\n    //    cout<<minWeight<<endl;\n         \n        for(int j=0; j<e; j++){ \n            int i=edges[j][1];\n            int w_j;\n            if (ctl_ps[i]==0){\n                MST.clear();\n                w_j=Kruskal(n, edges, MST, -1, j);  \n            }\n            if ((ctl_ps[i]||minWeight==w_j) && ctl[i]!=1){\n                pseudo_crt.push_back(i);\n                for(int k: MST)\n                    ctl_ps[edges[k][1]]=1;\n            }\n               \n        }\n        return {critical, pseudo_crt};\n    }\n};\n```
['Union Find', 'Graph', 'C++']