TC: O(n*4alpha)
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));
}
}
}
}
More readable way( same approach though)
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));
}
}
}
}
DFS approach:
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;
}
}
Top comments (0)