pknelakuditi.GitHub.io

q.add(start);
visited[start] = true;
        while (!q.isEmpty()) {
            int temp = q.remove();
            for (int i = 0; i < graph.get(temp).size(); i++) {
                if (!visited[i]) {
                    visited[i] = true;
                    q.add(i);
                }
            }
        }       

public static void dfs(ArrayList<ArrayList<Integer>> graph,int start){
q.add(start);
visited[start] = true;
        while(!s.isEmpty()){
            int temp=s.pop();
            ArrayList<Integer> neighbours=graph.get(temp);
            for(int n:neighbours){
                if(!visited[n]){
                    s.add(n);
                    visited[n]=true;
                }
            }

        }
}

public static int dijkstras(Vertex[] graph, int source, int destination) {
        boolean[] visited =new boolean[graph.length];
        Vertex current = graph[source];

        PriorityQueue<Vertex> pq = new PriorityQueue<Vertex>();
        //intially minDistance for each vertex would be Integer.MAXVALUE make start distance as zero
        current.minDistance=0;
        pq.add(current);
        while (!pq.isEmpty()) {
            current = pq.remove();
            if (current.id == destination) {
                break;
            }
            if(visited[current.id]){
                continue;
            }else{
                visited[current.id]=true;
            }

            //updating all the unvisited new neighbour values  and insert in pq
            for (Edge e : current.neighbors) {
                if((visited[e.end])){continue;}
                Vertex end = graph[e.end];
                int distance = e.distance;
                int newMin = distance + current.minDistance;
                if (newMin < end.minDistance  ) {
                    end.minDistance = newMin;
                    pq.add(end);
                }
            }

        }
        return graph[destination].minDistance;      

    }

    private static int PrimsAlgorithm(Vertex[] graph, int source) {
        PriorityQueue<Edge> pq=new PriorityQueue<Edge>();
        boolean[] visited=new boolean[graph.length];

        int cost=0;

        visited[source]=true;
        for(Edge e:graph[source].neighbors){
            pq.add(e);
        }

        while(!pq.isEmpty()){
            Edge current=pq.remove();

            if(visited[current.edge]){
                continue;
            }
            visited[current.edge]=true;
            cost=cost+current.cost;
            //adding all the unvisited neoghbours into the priority pq
            for(Edge e:graph[current.edge].neighbors){
                if(visited[e.edge]){
                    continue;
                }
                pq.add(e);

            }


        }


        return cost;
    }

public static class DisjointSets {
        int[] parents;

        public DisjointSets(int size) {
            parents = new int[size];
            for (int i = 0; i < size; i++) {
                parents[i] = i;
            }

        }

        public int find(int x) {
            if (parents[x] == x) {
                return x;
            }else{
                parents[x]=find(parents[x]);
                return parents[x];
            }

        }

        public void union(int x,int y){
            parents[find(x)]=find(y);
        }

    }

private static int kruskals(PriorityQueue<Edge> pq, int v) {
        DisjointSets ds=new DisjointSets(v);
        Edge current;
        int components=v;
        int cost=0;
        while(!pq.isEmpty()){
            current=pq.remove();
            if(ds.find(current.edge)==ds.find(current.oEdge)){
                continue;
            }
            components--;
            ds.union(current.edge,current.oEdge);
            cost+=current.cost;
        }
        if(components>1){
            return -1;
        }else{
            return cost;
        }

    }

struct Node *findLCA(struct Node* root, int n1, int n2)
{

   if (root == NULL) return NULL; 
   if (root->key == n1 || root->key == n2)
        return root;

    Node *left_lca  = findLCA(root->left, n1, n2);
    Node *right_lca = findLCA(root->right, n1, n2);

   if (left_lca && right_lca)  return root;

     return (left_lca != NULL)? left_lca: right_lca;
}

class BIT {
    int[] tree;
    public BIT(int n) {
        this.tree = new int[n];
    }
    int lsb(int x) {
        return x & -x;
    }
    void update(int i, int x) {
        while (i <= tree.length-1) {
            tree[i] += x;
            i += lsb(i);
        }
    }
    int query(int i) {
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= lsb(i);
        }
        return sum;
    }
}

private static int lis(int[] arr) {
        int max=1;
        mem=new int[arr.length];
        Arrays.fill(mem, 1);
        for(int i=1;i<arr.length;i++){
            for(int j=0;j<i;j++){
                if(arr[j]<arr[i] && mem[i]<mem[j]+1){
                    mem[i]=mem[j]+1;
                }
            }
            if(max<mem[i])max=mem[i];
        }

        return max;
    }

static int[] mem = new int[256];

    private static int longestSub(String a) {
        Arrays.fill(mem, -1);
        int pIndex;
        int current = 1;
        int max=1;

        mem[a.charAt(0)] = 0;
        for (int i = 1; i < a.length(); i++) {
            pIndex=mem[a.charAt(i)];
            //character not visited previously or it is not a part of Non repeating sequence
           if(pIndex==-1 || i-current>pIndex){
               current++;
           }else{
               //update max value if previous current value is greater than max till then
               if(current>max){
                   max=current;
               }
               current=i-pIndex;

           }
           mem[a.charAt(i)]=i;
        }
         if(current>max){
           max=current;
        }

        return max;
    }

static HashMap<Integer, Long> hm;

    public static long coinsT(int i) {
    hm = new HashMap<Integer, Long>();
        if (i < 12) {
            return i;
        }

        if (hm.containsKey(i)) {
            return hm.get(i);
        }
        long temp = coinsT(i / 2) + coinsT(i / 3) + coinsT(i / 4);
        hm.put(i, temp);
        return temp;
    }