[C++] Connected components (ACTUALLY EXPLAINED!)
Initial ideas\nSo we see a potentiallty disconnected undirected graph with some funky $\color{pink} &$ binary operator on the edge weights and we want to find t
# Initial ideas\nSo we see a potentiallty **disconnected** undirected graph with some funky $\\color{pink} &$ binary operator on the edge weights and we want to find the minimum **walk** from a source to a target.\n\nThere are two things about this problem that should make you immediately think **connected components**.\n\n- **walk** meaning we can cross an edge as many times as we wish\n- $\\color{pink} &$ is monotonically decreasing\n\nThe first part is pretty simple to understand \u2014 we can visit a whole lot of nodes. Specifically, all nodes in our connected component. Just something to consider for now.\n\nThe second part is crucial. The cumulative $\\color{pink} &$ operator can never increase as you increase the number of "summands". Like, take $\\color{cyan} [15,6,9]$, $\\color{violet} 15 \\geqslant 15 \\; & \\; 6 \\geqslant 15 \\; & \\;  6 \\; & \\; 9$\n\nThis is because $\\color{pink} &$ can only unset bits or keep them the same (when two numbers share a bit). It can never add new bits. \n\n## How does this help?\n\nWell! Since $\\color{pink} &$ is monotonically decreasing, it makes intuitive sense that we should try to feed it as many numbers as possible to minimise it. To do this, let\'s just take all the weights in the connected component and $\\color{pink} &$ them together. This works **IF** both source and target lie in the same connected component.\n\nIf they don\'t, well... It\'s impossible to ever find a path between them, as if there was one, they would be in the same connected component. Therefore, the answer should be $\\color{orange} -1$ in that case.\n\nA sly edge case I ran into is when the source and the target are the same. In this case, we ought to return $\\color{yellow} 0$.\n\n## The code\n```cpp\ntypedef vector<int> vi;\ntypedef pair<int,int> pi;\n\nstruct dsu {\n    vi parent, s;\n    int numCC;\n\n    dsu(int n) {\n        parent = vi(n);\n        numCC = n;\n        s = vi(n, 1);\n        for (int i = 1; i < n; ++i)\n            parent[i] = i;\n    }\n\n    int find(int v) {\n        if (v == parent[v])\n            return v;\n        return parent[v] = find(parent[v]);\n    }\n\n    void unite(int u, int v) {\n        u = find(u);\n        v = find(v);\n        if (u != v) {\n            numCC--;\n            if (s[u] < s[v])\n                swap(u, v);\n            parent[v] = u;\n            s[u] += s[v];\n        }\n    }\n\n    int getNumConnComp() const {\n        return numCC;\n    }\n\n\n};\n\nclass Solution {\npublic:\n    map<int,int> adj[(int) 1e5 + 3];\n\nvoid dfs(int v, dsu& d){\n    for (auto c: adj[v]){\n        if (d.find(c.first) == d.find(v))\n            continue;\n\n        d.unite(c.first,v);\n        dfs(c.first,d);\n    }\n}\n    \n    vector<int> minimumCost(int n, vector<vector<int>>& e, vector<vector<int>>& queries) {\n        dsu d(n);\n        for (auto x: e){\n        if (adj[x[0]].count(x[1])){\n            adj[x[0]][x[1]] &= x[2];\n        } else\n            adj[x[0]][x[1]] = x[2];\n        if (adj[x[1]].count(x[0])){\n            adj[x[1]][x[0]] &= x[2];\n        } else\n            adj[x[1]][x[0]] = x[2];\n    }\n\n    for (int i = 0; i <= n; ++i) // Collect all connected components\n        dfs(i,d);\n\n\n    map<int,int> m;\n\n    for (int i = 0; i < n; ++i){ \n// Store the & of all nodes in a specific CC in its representative in map m\n        if (m.count(d.find(i)))\n            for (auto c: adj[i]){\n                m[d.find(i)] &= c.second;\n            }\n        else {\n            m[d.find(i)] = (1ll << 30) - 1;\n            for (auto c: adj[i]) {\n                m[d.find(i)] &= c.second;\n            }\n        }\n    }\n    \n    vi ans;\n    for (auto x: queries){\n        int l = x[0];\n        int r = x[1];\n        if (l == r){\n            ans.emplace_back(0);\n            continue;\n        }\n        if (d.find(l) != d.find(r)){\n            ans.emplace_back(-1);\n        } else\n            ans.emplace_back(m[d.find(l)]);\n    }\n        return ans;\n    }\n};\n```\n\n### Time complexity:\n$\\color{Fuchsia} O\\left((n\\cdot\\alpha(n) + q) \\log_2 (n)\\right)$ due to use of the DSU structure and map invocation.\n\n### Space complexity:\n$\\color{Fuchsia} O(n + q)$\n
['Union Find', 'Graph', 'C++']