Intuitive C++ solution using Kruskal's algorithm
Intuition\n Describe your first thoughts on how to solve this problem. \nBrute force for each edge to find critical and non-critical edges.\nIf an edge is neith
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBrute force for each edge to find critical and non-critical edges.\nIf an edge is neither critical nor non-critical edge then it must be pseudo-critical.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n**Idea to find critical edges:**\nTry to remove an edge from graph and construct MST, if weight is increased then it is critical edge.\n\n**Idea to find non-critical edges:**\nIf by forcefully including edge i, we get higher weight than original, then it must be non-critical edge(one which is not in any MST). Because critical edges must be in MST, and for pseudo-critical, by forcefully including edge, we can still build an MST of same weight as original.\n\n# Complexity\n- Time complexity:\n- O(E*ElogV) -> Running Kruskal\'s E times\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```\nclass DSU {\n    int par[101], size[101];\npublic:\n    DSU() {\n        for(int i = 0; i < 101; i++) {\n            par[i] = i;\n            size[i] = 1;\n        }\n    }\n\n    int find(int u) {\n        if(u == par[u]) return u;\n        return par[u] = find(par[u]);\n    }\n\n    void merge(int u, int v) {\n        u = find(u); v = find(v);\n        if(u == v) return;\n        if(size[u] < size[v]) swap(u, v);\n        par[v] = u;\n        size[u] += size[v];\n    }\n};\n\nclass Solution {\n    vector<pair<int, int>> E;           // {weight, index} -> index in edges of two nodes\n    bool critical[201], non_critical[201];\n    int m;\n\n    int mst_skip(vector<vector<int>>& edges, int skip, int n) {\n        E.clear();\n        for(int i = 0; i < m; i++) {\n            if(i == skip) continue;\n            vector<int> &e = edges[i];\n            E.push_back({e[2], i});\n        }\n        sort(E.begin(), E.end());\n        struct DSU dsu;\n        int total = 0;\n        for(int i = 0; i < E.size(); i++) {\n            int ind = E[i].second;\n            int w = E[i].first, u = edges[ind][0], v = edges[ind][1];\n\n            if(dsu.find(u) == dsu.find(v)) continue;\n            total += w;\n            dsu.merge(u, v);\n        }\n\n        // if edge "skip" happens to be a bridge, then the graph will get disconnected and MST cannot be formed(or formed with infinite weight)\n        // check for parents\n        for(int i = 0; i < n; i++) {\n            if(dsu.find(i) != dsu.find(0)) return 1e9;\n        }\n\n        return total;\n    }\n\n    int mst_include(vector<vector<int>>& edges, int include, int n) {\n        E.clear();\n        struct DSU dsu;\n        int total = 0;\n        for(int i = 0; i < m; i++) {\n            vector<int> &e = edges[i];\n            if(i == include) {\n                int w = e[2], u = e[0], v = e[1];\n                dsu.merge(u, v);\n                total += w;\n                continue;\n            }\n            E.push_back({e[2], i});\n        }\n        sort(E.begin(), E.end());\n        for(int i = 0; i < E.size(); i++) {\n            int ind = E[i].second;\n            int w = E[i].first, u = edges[ind][0], v = edges[ind][1];\n\n            if(dsu.find(u) == dsu.find(v)) continue;\n            total += w;\n            dsu.merge(u, v);\n        }\n\n        return total;\n    }\npublic:\n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {\n        // critical edges are those, which if removed from the graph and MST is then constructed, the weight of MST would be more than the original MST weight.\n\n        vector<vector<int>>ans(2);\n        m = edges.size();\n        int original_weight = mst_skip(edges, -1, n);\n\n        // brute force for all edges to find if it is critical or not\n        // TC = O(m * m log n)\n        // try to remove an edge from graph and construct MST, if weight is increased then it is critical edge.\n        for(int i = 0; i < m; i++) {\n            int weight = mst_skip(edges, i, n);\n            if(weight > original_weight) {\n                // i is critical edge\n                ans[0].push_back(i);\n                critical[i] = 1;\n            } \n        }\n\n        // brute force for all edges to find if it is non-critical or not\n        // TC = O(m * m log n)\n        // If by forcefully including edge i, we get higher weight than original, then it must be non-critical edge(one which is not in any MST). Because critical edges must be in MST, and for pseudo-critical, by forcefully including edge, we can still build an MST of same weight as original.\n        for(int i = 0; i < m; i++) {\n            int weight = mst_include(edges, i, n);\n            if(weight > original_weight) {\n                // i is non-critical\n                non_critical[i] = 1;\n            }\n        }\n\n        for(int i = 0; i < m; i++) {\n            if(!critical[i] && !non_critical[i]) ans[1].push_back(i);\n        }\n\n        return ans;\n    }\n\n};\n```
['Minimum Spanning Tree', 'C++']