This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
using namespace std; | |
int partition (int arr[], int low, int high) | |
{ | |
int pivot=low+rand()%(high-low+1); | |
swap(arr[pivot],arr[high]); | |
int i=low; | |
for(int j=low;j<high;j++){ | |
if(arr[j]<arr[high]){ |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// finding bridges in graph in O(n+m) | |
// https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=737 | |
#include <bits/stdc++.h> | |
using namespace std; | |
int timer; | |
void dfs(int s,int par,vector<int>adj[],vector<bool>&vis,vector<int>&tin,vector<int>&low,vector<pair<int,int>>&ans){ | |
vis[s]=1; | |
tin[s]=low[s]=++timer; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// author: 08vivek08 | |
#include <bits/stdc++.h> | |
using namespace std; | |
#define int long long | |
int mod = 1e9 + 7; | |
struct segment_tree |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// // Binary Indexed Tree or Fenwick Tree | |
// // 1 based indexing of array | |
// #include <bits/stdc++.h> | |
// using namespace std; | |
// int sum(int k, int tree[]){ | |
// int s=0; | |
// while(k>=1){ | |
// s+=tree[k]; | |
// k-=k&-k; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Directed Acyclic GRAPH | |
// counting number of paths | |
// paths (x) denote the number of paths from node a to node x . As a base case paths(a)=1 | |
// vertices start from 1 onwards | |
#include <bits/stdc++.h> | |
using namespace std; | |
class Graph{ | |
int vertices; | |
vector<int>*adj; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Kruskal's algorithm to find minimum spanning tree | |
// O(mlog(m)) time complexity | |
// vertices start from 1 onwards | |
#include <bits/stdc++.h> | |
using namespace std; | |
const int INF=1e7; | |
class Graph{ | |
int v,e; | |
vector<tuple<int,int,int>>edges; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
using namespace std; | |
const int Max_char=26; | |
struct trie{ | |
trie *child[Max_char]; | |
bool isendofword; | |
}; | |
trie *getnode(){ | |
trie *p=new trie; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Directed Acyclic GRAPH | |
// Topological sort | |
// vertices start from 1 onwards | |
#include <bits/stdc++.h> | |
using namespace std; | |
class Graph{ | |
int vertices; | |
vector<int>*adj; | |
bool cycle=false; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Bellman ford on weighted GRAPH | |
// O(n*m) time complexity | |
// GRAPH's edge list representation | |
// vertices start from 1 onwards | |
// can detect negative cycle in graph | |
#include <bits/stdc++.h> | |
using namespace std; | |
const int INF=1e7; | |
int main() { |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// DIJKSTRA on weighted GRAPH | |
// O(n+mlog(m)) time complexity | |
// vertices start from 1 onwards | |
// can't work in case of negative edges | |
#include <bits/stdc++.h> | |
using namespace std; | |
const int INF=1e7; | |
class Graph{ | |
int vertices; |
NewerOlder