Shortest Reach in a Graph (CTCI)

Problem: Shortest Reach in a Graph

class Graph {
    public:
        int node;
        vector<int> adj[1001];
        Graph(int n) {
            node = n;
        }
    
        void add_edge(int u, int v) {
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
    
        vector<int> shortest_reach(int start) {
            vector<int> dist (node);
            for(int i=0;i<node;i++)
                dist[i]=-1;
            dist[start]=0;
            queue<int>Q;
            Q.push(start);
            while(!Q.empty())
            {
                int tmp = Q.front();
                for(int i=0;i<adj[tmp].size();i++)
                    if(dist[adj[tmp][i]]==-1)
                    {
                        dist[adj[tmp][i]] = dist[tmp]+6;
                        Q.push(adj[tmp][i]);
                    }
                Q.pop();
            }
            return dist;
        }
    
};

int main() {
    int queries;
    cin >> queries;
        
    for (int t = 0; t < queries; t++) {
      
      int n, m;
        cin >> n;
        // Create a graph of size n where each edge weight is 6: 
        Graph graph(n);
        cin >> m;
        // read and set edges
        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            u--, v--;
            // add each edge to the graph
            graph.add_edge(u, v);
        }
      int startId;
        cin >> startId;
        startId--;
        // Find shortest reach from node s
        vector<int> distances = graph.shortest_reach(startId);

        for (int i = 0; i < distances.size(); i++) {
            if (i != startId) {
                cout << distances[i] << " ";
            }
        }
        cout << endl;
    }
    
    return 0;
}

Connected Cell in a Grid (CTCI)

Problem: Connected Cell in a Grid

int n, m;
bool vis[10][10];

void dfs(vector< vector<int> > grid, int row, int col, int *cnt)
{
    vis[row][col]=1;
    *cnt = *cnt + 1;
    for(int i=-1;i<=1;i++)
        for(int j=-1;j<=1;j++)
        {
            if(!i && !j) continue;
            if(row+i>=0 && row+i<n && col+j>=0 && col+j<m)
                if(!vis[row+i][col+j])
                    if(grid[row+i][col+j]==1)
                        dfs(grid, row+i, col+j, cnt);
        }
   return;
}

int get_biggest_region(vector< vector<int> > grid) {
    int row = grid.size(), col = grid[0].size(), mx=0, tmp;
    memset(vis, 0, sizeof(vis));
    for(int i=0;i<row;i++)
        for(int j=0;j<col;j++)
            if(!vis[i][j] && grid[i][j])
            {
                tmp=0;
                dfs(grid, i, j, &tmp);
                mx = max(mx, tmp);
            }
     return mx;
}

int main(){
    cin >> n;
    cin >> m;
    vector< vector<int> > grid(n,vector<int>(m));
    for(int grid_i = 0;grid_i < n;grid_i++){
       for(int grid_j = 0;grid_j < m;grid_j++){
          cin >> grid[grid_i][grid_j];
       }
    }
    cout << get_biggest_region(grid) << endl;
    return 0;
}

Ice Cream Parlor (CTCI)

Problem: Ice Cream Parlor

#include <bits/stdc++.h>
using namespace std;

class IceCream {
    
    public: 
        int flavor; 
        int index;

        IceCream(int flavor, int index) {
            this->flavor = flavor;
            this->index = index;
       }
};
    
int binarySearch(int first, int last, vector<IceCream> arr, int search) {
   int mid;
   while(first<=last)
   {
       mid = (first+last)>>1;
       if(arr[mid].flavor == search)
           return arr[mid].index;
       if(arr[mid].flavor < search)
           first = mid+1;
       else last =  mid-1;
   }
   return -1;
}

bool compare(IceCream a, IceCream b)
{
    if(a.flavor != b.flavor) return a.flavor<b.flavor;
    return a.index<b.index;
}

int main() {
    int t;
    int n, m;
    cin >> t;
    for(int test = 0; test < t; test++) {       
        cin >> m >> n;
        vector<IceCream> arr;
        arr.reserve(n); 

        for (int i = 0; i < n; i++) {
            int cost;
            cin >> cost;
            arr.push_back(IceCream(cost, i + 1));
        }

        sort(arr.begin(), arr.end(), compare);
        for(int i = 0; i < n - 1 ; i++) {
            int search = m - arr[i].flavor;
            if(search >= arr[i].flavor) {
                int index = binarySearch( i + 1, n - 1, arr, search);
                if( index != -1 ) {
                    cout << min(arr[i].index, index) << " " << max(arr[i].index, index) << endl;
                    break;

                }
            }
        }
    }
}

Counting Inversions (CTCI)

Problem: Counting Inversions

long long merge(vector<int> *a, int st, int mid, int ed)
{
    vector<int> v(ed-st+1);
    long long cnt=0;
    int i=st, j=mid+1, vi=0;
    while(i<=mid && j<=ed)
    {
        if(a->at(i) <= a->at(j))
            v[vi++] = a->at(i++);
        else 
        {
            cnt += mid-i+1;
            v[vi++] = a->at(j++);
        }
    }
    while(i <= mid)
        v[vi++] = a->at(i++); 
    while(j <= ed)
        v[vi++] = a->at(j++);
    for(int i=0;i<vi;i++)
        a->at(st++) = v[i];
    
    return cnt;
}

long long mergeSort(vector<int> *a, int st, int ed)
{
    if(st>=ed) return 0;
    long long cnt=0;
    int mid = st + (ed-st)/2;
    cnt += mergeSort(a, st, mid);
    cnt += mergeSort(a, mid+1, ed);
    cnt += merge(a, st, mid, ed);
    return cnt;
}

long long count_inversions(vector<int> a) {
   int al = a.size();
   return mergeSort(&a, 0, al-1); 
}

int main(){
    int t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        int n;
        cin >> n;
        vector<int> arr(n);
        for(int arr_i = 0;arr_i < n;arr_i++){
           cin >> arr[arr_i];
        }
        cout << count_inversions(arr) << endl;
    }
    return 0;
}