C++ Compute Connected Components, 3ms Beats 94%, O(N) Best Time, O(N*Log(N)/2) Worst Time, O(N) Space


  • 0
    M

    In my algorithm I keep track of all current connected components in a graph. If a new edge is added I check if both ends belong to different components, then I join both components together into one (by updating info of smaller of two components), if ends of edge belong to same component it means that edge introduces cycle and this first edge is an answer to output. v2c is a mapping from vertex number to component number it belongs, c2v is a mapping from component number to vertex number, vn is a mapping from vertex number to next vertex in linked list of a connected component, cs is component size (number of vertices). Complexity analysis: for each added edge I traverse smaller one of components to connect it to another component, in worst case to half the amount of components (by joining them) we need to traverse N/2 nodes with total Log(N) halving events, so total time is O(N*Log(N)/2), in best case if we add 1 node at a time to current component then we need to traverse just 1 node each time so O(N) total time of traversal. Space occupied is O(N).

    class Solution {
    public:
        vector<int> findRedundantConnection(vector<vector<int>>& edges) {
            vector<int> v2c, c2v, vn, cs;
            for (auto& e: edges) {
                while (v2c.size() < max(e[0], e[1])) {
                    vn.push_back(-1);
                    c2v.push_back(v2c.size());
                    v2c.push_back(v2c.size());
                    cs.push_back(1);
                }
                if (v2c[e[0] - 1] == v2c[e[1] - 1]) return e;
                int c0 = v2c[e[0] - 1], c1 = v2c[e[1] - 1];
                if (cs[c0] < cs[c1]) swap(c0, c1);
                for (int vf = c2v[c1], v = vf; v != -1; v = vn[v]) {
                    v2c[v] = c0;
                    if (vn[v] == -1) {
                        vn[v] = c2v[c0];
                        c2v[c0] = vf;
                        c2v[c1] = -1;
                        cs[c0] += cs[c1];
                        break;
                    }
                }
            }
            return {0, 0};
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.