3108. Minimum Cost Walk in Weighted Graph

class Solution { public int[] minimumCost(int n, int[][] edges, int[][] query) { Disjoint d = new Disjoint(n); Map<Integer,Integer> map = new HashMap<>(); for(int edge[] :edges){ int u = edge[0]; int v = edge[1]; int w = edge[2]; //if parents are not same then union them (will create common parent for both u and v) if(d.findParent(u) != d.findParent(v)){ //since u and v will be unioned there values will also be updated as below //distance value of the first part/component int diU = map.getOrDefault(d.findParent(u),w); //distance value of the second part/component int diV = map.getOrDefault(d.findParent(v),w); //union u and v componts d.union(u,v); int p = d.findParent(u); //get parent of u or v does not matter their parents would be same after their union map.put(p, diU & diV & w); // update the common distance at the parent level ( both the components will be come one unified component and they will have a common smaller distance created by &) } else{ // if they have same common parent then we just have to updated the distance by & w at the parent node int p = d.findParent(u); map.put(p, map.get(p) & w); } } int result[] = new int[query.length]; for(int i =0;i<query.length;i++){ int u = query[i][0]; int v = query[i][1]; // only if the parent are same is when there is an edge between the nodes(direct edge or indirect edge) //and the parent node will have the the lowest values by & (computed in the above part) if(d.findParent(u) == d.findParent(v)){ result[i] = map.get(d.findParent(u)); } else result[i] = -1;// otherwise there is no direct/indirect edge between u and v } return result; } } class Disjoint{ List<Integer> parent = new ArrayList<>(); List<Integer> rank = new ArrayList<>(); public Disjoint(int n){ for(int i = 0;i< n;i++){ parent.add(i); rank.add(1); } } public int findParent(int n){ if(n == parent.get(n)) return n; else{ parent.set(n, findParent(parent.get(n))); return parent.get(n); } } public void union(int u, int v){ u = findParent(u); v = findParent(v); if(u!=v){ if(rank.get(u) > rank.get(v)){ parent.set(v,u); } else if(rank.get(u) < rank.get(v)){ parent.set(u,v); } else{ parent.set(v,u); rank.set(u, rank.get(v) + rank.get(u)); } } } } 

class Solution { public int[] minimumCost(int n, int[][] edges, int[][] query) { Disjoint d = new Disjoint(n); Map<Integer,Integer> map = new HashMap<>(); // do the union of all the nodes to form all the components for(int edge[] :edges){ int u = edge[0]; int v = edge[1]; int w = edge[2]; if(d.findParent(u) != d.findParent(v)){ d.union(u,v); } } //iterate over the edges to update the min cost for(int edge[] :edges){ int u = edge[0]; int v = edge[1]; int w = edge[2]; int parent = d.findParent(u);// parent of u and v are same ( as they have already been unified in the above iteration) if(!map.containsKey(parent)){ map.put(parent,w); } else map.put(parent, map.get(parent) & w);// if the parent is alredy present just & the current weight } int result[] = new int[query.length]; for(int i =0;i<query.length;i++){ int u = query[i][0]; int v = query[i][1]; // only if the parent are same is when there is an edge between the nodes(direct edge or indirect edge) //and the parent node will have the the lowest values by & (computed in the above part) if(d.findParent(u) == d.findParent(v)){ result[i] = map.get(d.findParent(u)); } else result[i] = -1;// otherwise there is no direct/indirect edge between u and v } return result; } } class Disjoint{ List<Integer> parent = new ArrayList<>(); List<Integer> rank = new ArrayList<>(); public Disjoint(int n){ for(int i = 0;i< n;i++){ parent.add(i); rank.add(1); } } public int findParent(int n){ if(n == parent.get(n)) return n; else{ parent.set(n, findParent(parent.get(n))); return parent.get(n); } } public void union(int u, int v){ u = findParent(u); v = findParent(v); if(u!=v){ if(rank.get(u) > rank.get(v)){ parent.set(v,u); } else if(rank.get(u) < rank.get(v)){ parent.set(u,v); } else{ parent.set(v,u); rank.set(u, rank.get(v) + rank.get(u)); } } } } 

class Solution { int minCost[] = new int[1]; // to keep track of cost for each component public int[] minimumCost(int n, int[][] edges, int[][] query) { Map<Integer,List<Pair>> adj = new HashMap<>(); for(int i =0;i< n;i++){ adj.put(i, new ArrayList<>()); } for(int edge[] : edges){ int u = edge[0]; int v = edge[1]; int w = edge[2]; List<Pair> list = adj.getOrDefault(u, new ArrayList<>()); list.add(new Pair(v,w)); adj.put(u, list); List<Pair> list2 = adj.getOrDefault(v, new ArrayList<>()); list2.add(new Pair(u,w)); adj.put(v, list2); } int visited[] = new int[n]; // along with keep track of what node is visited it will also tell us component to which the node belogs Map<Integer,Integer> componentCost = new HashMap<>(); int currentComponent =1; for(int i=0;i< n;i++){ if(visited[i] ==0){ minCost[0] = Integer.MAX_VALUE; // to make sure all the binary value are 1 so that it does not affect the actual & results we will get in the dfs from the edges of this compnent dfs(i,adj,visited,currentComponent); componentCost.put(currentComponent, minCost[0]); currentComponent+=1; // after this we will try to traverse the next component if present } } int result[] = new int[query.length]; for(int i =0;i< query.length;i++){ int u = query[i][0]; int v = query[i][1]; // if u and v are part of the same component if(visited[u] == visited[v]){ result[i] = componentCost.get(visited[u]); } else result[i] = -1; } return result; } public void dfs(int node, Map<Integer,List<Pair>> adj,int [] visited, int currentComponent){ visited[node] = currentComponent; //insted of putting 1 we will put the component no. of this node, this will help us greatly in the query part for(Pair p : adj.get(node)){ int adjNode = p.n; minCost[0]&=p.w;// even if it is already visited node then also we want to & all the the weights to get the min cost for the current component if(visited[adjNode]==0){ dfs(adjNode, adj, visited,currentComponent); } } } } class Pair{ int n; int w; public Pair(int n ,int w){ this.n = n; this.w = w; } }