Beats 100% ✅ || Detailed explanation using BFS 🔥 || Very Easy to understand for beginners 💯
Intuition\nThe problem requires finding the minimum cost of a walk in an undirected weighted graph where the cost is defined as the bitwise AND of the weights o
# Intuition\nThe problem requires finding the minimum cost of a walk in an undirected weighted graph where the cost is defined as the bitwise AND of the weights of the edges traversed during the walk. We need to handle multiple queries for different starting and ending vertices.\n\n--- \n\n# Approach\n- Construct the adjacency list representation of the graph and initialize the cost array `c`.\n- For each edge, update the cost array `c` by performing bitwise AND with the edge weight.\n- Use a breadth-first search (BFS) traversal to find connected components in the graph and update the cost array `c` for each component.\n- For each query, check if the starting and ending vertices belong to the same connected component. If they do, return the minimum cost of the connected component; otherwise, return `-1`.\n\n---\n\n# Complexity\n- ### Time complexity:\n    - Constructing the adjacency list: `O(E)`, where `E` is the number of edges.\n    - BFS traversal: `O(V + E)`, where `V` is the number of vertices.\n    - Processing queries: `O(Q)`, where `Q` is the number of queries.\n    - Overall time complexity: `O(V + E + Q)`.\n\n\n- ### Space complexity:\n    - Space for the adjacency list: `O(E)`.\n    - Space for the cost array c: `O(V)`.\n    - Space for the queue and group array during BFS: `O(V)`.\n    - Overall space complexity: `O(V + E)`.\n\n--- \n\n![66dabafc-1e25-4e05-b54d-4157c3ebe2af_1708833865.8845494.jpeg](https://assets.leetcode.com/users/images/05bc854d-d245-4a62-ad0b-0199d37010a7_1712463103.7328107.jpeg)\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> minimumCost(int N, vector<vector<int>>& edges, vector<vector<int>>& queries) {\n    vector<vector<int>> adj(N); // Adjacency list\n    vector<int> c(N, (1 << 30) - 1); // Cost array, initialized with maximum possible value\n    \n    // Construct adjacency list and update cost array\n    for (vector<int> edge : edges) {\n        int u = edge[0], v = edge[1], k = edge[2];\n        adj[u].push_back(v);\n        adj[v].push_back(u);\n        c[u] = c[u] & k; // Update cost with bitwise AND\n        c[v] = c[v] & k;\n    }\n    \n    // BFS to find connected components and update cost array for each component\n    queue<int> q;\n    vector<int> group(N, -1); // Group array to store component group of each vertex\n    for (int i = 0; i < N; i++) {\n        if (group[i] == -1) {\n            group[i] = i; // Assign component group ID\n            q.push(i);\n            while (!q.empty()) {\n                int u = q.front(); q.pop();\n                c[i] = c[i] & c[u]; // Update cost with bitwise AND of all vertices in the component\n                for (int v : adj[u]) {\n                    if (group[v] == -1) {\n                        group[v] = i;\n                        q.push(v);\n                    }\n                }\n            }\n        }\n    }\n    \n    // Process queries\n    vector<int> res;\n    for (vector<int> query : queries) {\n        int s = query[0], t = query[1];\n        if (s == t) {\n            res.push_back(0); // Same starting and ending vertex\n        } else {\n            if (group[s] == group[t]) {\n                res.push_back(c[group[s]]); // Same connected component\n            } else {\n                res.push_back(-1); // Different connected components\n            }\n        }\n    }\n    return res;\n}\n};\n```
['Bit Manipulation', 'Graph', 'C', 'C++', 'Java']