Bellman_ford algo

#include <iostream>

using namespace std;

void main()
{


	//system("pause"); // in visual studio 17-
}

#include <iostream>
using namespace std;

int main() {
    int x = 5;
    int y = 6;
    int sum = x + y;
    // Integers (whole number)
    int age = 21;
    int year = 2023;
    int days = 7;
    int hours = 4.5; //this is able becuase int only contains whole number. The outpute would be 4 not 4.5
    
    // double (number including decimal)
    double price = 10.98;
    double gpa = 2.5;
    double temperature = 25.1;
    
    // char (single character)
    char grade = 'A';
    char intitals = 'B';
    char currency = '$';
    
    // booleen (True or false)
    bool student = false;
    bool power = true;
    bool  forSale = true;
    
    // stirng (objects that represents a sequence of text)
    std::string name = "bro";
    std::string day = "Friday";
    std::string food = "Pizza";
    std::string adress = "123 fake st.";
    cout << "Hello " << name;
   cout << "You are " << age << " years old";

    return 0;
}

vector<int> sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false; // 0 and 1 are not prime numbers

    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    std::vector<int> primes;
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }

    return primes;
}

 vector<int> parent;
    vector<int> rank;
    // path compression code 
    int find(int i){
        if(i == parent[i]) return i;
       return parent[i] = find(parent[i]);
    }
    // optimised Union fn 
    void Union(int x, int y){
        int x_parent = find(x);
        int y_parent = find(y);
        
        if(x_parent == y_parent){
            return;
        }else if(rank[x_parent] > rank[y_parent]){
            parent[y_parent] = x_parent;
        }else if(rank[y_parent] > rank[x_parent]){
            parent[x_parent] = y_parent;
        }else{
            parent[x_parent] = y_parent;
            rank[y_parent]++;
        }
    }

vector<int> bellman_ford(int V, vector<vector<int>>& edges, int S) {
       vector<int> dis(V,1e8);
       dis[S] = 0;
       for(int cnt = 0; cnt<=V-1; cnt++){
           for(auto edge : edges){
               int u = edge[0];
               int v = edge[1];
               int w = edge[2];
               if(dis[u] != 1e8 and dis[u] + w < dis[v]){
                   dis[v] = dis[u] + w;
               }
           }
       }
       
       // Check for negative weight cycles
       for(auto edge : edges) {
           int u = edge[0];
           int v = edge[1];
           int w = edge[2];
           if(dis[u] != 1e8 && dis[u] + w < dis[v]) {
               // If we can still relax an edge, there is a negative weight cycle
               return {-1}; // Return an empty vector to indicate the presence of a negative cycle
           }
       }
       
       return dis;
    }

bool detectLoop (node* head) {
  if (head == NULL) {
    return false;
  }
  map <node*, bool> visited;
  node* temp = head;
  while (temp != NULL) {
    if (visited[temp] == true) {
      return true;
    }
    visited[temp] = true;
    temp = temp -> next;
  }
  return false;
}

bool floyedDetectionLoop (node* head) {
  if (head == NULL) {
    return false;
  }
  node* fast = head;
  node* slow = head;
  while (fast != NULL && slow != NULL) {
    fast = fast -> next;
    if (fast -> next == NULL) {
      fast = fast -> next;
    }
    slow = slow -> next;
    if (fast == slow) {
      return true;
    }
    
  }
  return false;
}

node *floyedDetectionLoop(node *head) {
  if (head == NULL) {
    return NULL;
  }
  node *fast = head;
  node *slow = head;
  while (fast != NULL && slow != NULL) {
    fast = fast->next;
    if (fast->next != NULL) {
      fast = fast->next;
    }
    slow = slow->next;
    if (fast == slow) {
      return slow;
    }
  }
  return NULL;
}

node *getStartingNode(node *head) {
  if (head == NULL) {
    return NULL;
  }
  node *intersection = floyedDetectionLoop(head);
  node *slow = head;
  while (slow != intersection) {
    slow = slow->next;
    intersection = intersection->next;
  }
  return slow;
}

void removeLoop(node *head) {
  if (head == NULL) {
    return;
  }
  node *startOfLoop = getStartingNode(head);
  node *temp = startOfLoop;
  while (temp->next != startOfLoop) {
    temp = temp->next;
  }
  temp->next = NULL;
  cout << "loop is removed " << endl;
}

node* sortList (node* head) {
  int zeroCount = 0;
  int oneCount = 0;
  int twoCount = 0;
  node* temp = head;
  while (temp != NULL) {
    if (temp -> data == 0) {
      zeroCount++;
    }
    else if (temp -> data == 0) {
      oneCount++;
    }
    else if (temp -> data == 0) {
      twoCount++;
    }
    temp = temp -> next;
  }
  temp = head;
  while (temp != NULL) {
    if (zeroCount != 0) {
      temp -> data = 0;
      zeroCount--;
    }
    else if (oneCount != 0) {
      temp -> data = 1;
      oneCount--;
    }
    else if (twoCount != 0) {
      temp -> data = 2;
      twoCount--;
    }
    temp = temp -> next;
  }
  return temp;
}

node *findMid(node *head) {
  node *slow = head;
  node *fast = head->next;
  while (fast != NULL && fast->next != NULL) {
    slow = slow->next;
    fast = fast->next->next;
  }
  return slow;
}

node *merge(node *left, node *right) {
  if (left == NULL) {
    return right;
  }
  if (right == NULL) {
    return left;
  }
  node *ans = new node(-1);
  node *temp = ans;
  while (left != NULL && right != NULL) {
    if (left->data < right->data) {
      temp->next = left;
      temp = left;
      left = left->next;
    } else {
      temp->next = right;
      temp = right;
      right = right->next;
    }
  }
  while (left != NULL) {
    temp->next = left;
    temp = left;
    left = left->next;
  }
  while (right != NULL) {
    temp->next = right;
    temp = right;
    right = right->next;
  }
  ans = ans->next;
  return ans;
}

node *mergeSort(node *head) {
  // base case
  if (head == NULL || head->next == NULL) {
    return head;
  }
  // breaking the linked list into two halves
  node *mid = findMid(head);
  node *first = head;
  node *second = mid->next;
  mid->next = NULL;
  // recursive call
  first = mergeSort(first);
  second = mergeSort(second);
  // merging the two sorted halves
  node *result = merge(first, second);
  return result;
}

bool isValidParenthesis (string expression) {
  stack<char> s;
  for (int i = 0; i < expression.length(); i++) {
    char ch = expression[i];
    // if opening bracket push it to stack
    // if closing bracket, pop from stack, check if the popped element is the                 matching opening bracket
    if (ch == '(' || ch =='{' || ch == '[') {
      s.push(ch);
    }
    else {
      // for closing bracket
      if (!s.empty()) {
        char top = s.top();
        if ((ch == ')' && top == '(') || (ch == '}' && top == '{') || (ch == ']' &&               top == '[')) {
          s.pop();
        }
      }
      else {
        return false;
      }
    }
  }
  if (s.empty()) {
    return true;
  }
  else {
    return false;
  }
}