C++ Graph Theory Sample Cheat Sheet

///Adjacency Matrix////////////////////
int V, E, A, B, W, g[1005][1005];
cin >> V >> E; memset(g, -1, sizeof(g));
for (int i = 0; i < E; i++) {
    cin >> A >> B >> W;
    //Weight, can set for both or single direction
    g[A][B] = W; 
    g[B][A] = W;
}

///Adjacency List//////////////////////
vector<pair<int, int> > g[1005];
int V, E, A, B, W;
cin >> V >> E;
for (int i = 0; i < E; i++) {
    cin >> A >> B >> W;
    g[A].push_back(make_pair(B, W));
    g[B].push_back(make_pair(A, W)); 
}

//initialise dist[i][j] to infinity at the start
for (int k=0;k<n;k++)
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
        // if there is a shorter path through node k, take it!
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);w

//Lol just copied from hackerearth website
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <utility>

using namespace std;
const int MAX = 1e4 + 5;
typedef pair<long long, int> PII;
bool marked[MAX];
vector <PII> adj[MAX];

long long prim(int x)
{
    priority_queue<PII, vector<PII>, greater<PII> > Q;
    int y;
    long long minimumCost = 0;
    PII p;
    Q.push(make_pair(0, x));
    while(!Q.empty())
    {
        // Select the edge with minimum weight
        p = Q.top();
        Q.pop();
        x = p.second;
        // Checking for cycle
        if(marked[x] == true)
            continue;
        minimumCost += p.first;
        marked[x] = true;
        for(int i = 0;i < adj[x].size();++i)
        {
            y = adj[x][i].second;
            if(marked[y] == false)
                Q.push(adj[x][i]);
        }
    }
    return minimumCost;
}

int main()
{
    int nodes, edges, x, y;
    long long weight, minimumCost;
    cin >> nodes >> edges;
    for(int i = 0;i < edges;++i)
    {
        cin >> x >> y >> weight;
        adj[x].push_back(make_pair(weight, y));
        adj[y].push_back(make_pair(weight, x));
    }
    // Selecting 1 as the starting node
    minimumCost = prim(1);
    cout << minimumCost << endl;
    return 0;
}

ll lca(ll N,ll a,ll b){
    if(depth[a]<depth[b]) swap(a,b);
    //Equalise depth
    for(ll k=log2(N);k>=0;k--){
        ll parent = find_parent(a,k);//p[a][k]
        if(parent!=-1 && depth[parent]>=depth[b]){
            a=parent;
        }
    }
    if (a==b)return a;
    //Jump parent by parent
    for(ll k=log2(N);k>=0;k--){
        ll parent = find_parent(a,k);//p[a][k]
        ll parentb = find_parent(b,k);//p[b][k]
        if(parent!=parentb)a=parent,b=parentb;
    }
    return p[a][0];
}

vector<int> g[100005];
queue<pair<int, int> > q;
int dist[1000005];
fill(dist, dist+1000005, -1);
while (!q.empty()) {
    int v = q.front().first;
    int d = q.front().second;
    q.pop();
    if (dist[v] != -1) continue; //Visited
    dist[v] = d;
    for (int i = 0; i < g[v].size(); i++) {
        q.push(make_pair(g[v][i], d+1));
    }
}

dist[s]=0; //dist all others = INF
for (int i=0; i<N-1; i++){
    for (int j=0; j<E; j++){
        // if path is shorter through node u, take it!
        dist[v] = min(dist[v], dist[u]+cost);
    }
}

int root (int x ) {
    if (x == parent [x]) return x ;
    return root (parent[x]) ;
}
bool is_connected (int x,int y) {
    return root (x) == root(y) ;
}
void connect ( int x , int y ) {
    int root_x = root (x);
    int root_y = root (y);
    if (root_x != root_y)
        parent [root_x] = root_y ;
}

////For Ranking//////////////////////
int rank[N];
void connect (int x , int y) {
    int root_x = root (x) , root_y = root (y) ;
    if (root_x == root_y) return ; // same root
    if (rank[root_x] > rank[root_y]) {
        parent[root_y] = root_x ;
    } else if (rank[root_x] < rank[root_y]) {
        parent[root_x] = root_y ;
    } else {
        parent[root_y] = root_x ;
        rank[root_x]++;
    }
}

vector <tuple<int,int,int> > edges ; // weight,node A,node B
sort (edges.begin(), edges.end ()) ;
int total_weight = 0;
for (auto e : edges) {
    int weight, a, b;
    tie (weight,a,b) = e ;
    if (root(a) == root(b)) // taking this edge will cause a cycle
        continue;
    total_weight += weight ; // take this edge
    connect (a, b) ; // connect them in the UFDS
}

bool vis[N];
vector<int> adjList[N];
void dfs(int node) {
    if (vis[node]) return;
    vis[node] = true;
    for (int a = 0; a < (int)adjList[node].size(); ++a)
        dfs(adjList[node][a]);
}

///Iterative////////////////////////////////
bool vis[N];
vector<int> adjList[N];
stack<int> S;
while (!S.empty()) {
    int node = S.top();
    S.pop();
    if (vis[node]) continue;
    vis[node] = true;
    for (int a = 0; a < (int)adjList[node].size(); ++a)
        S.push(adjList[node][a]);
}

vector<pair<int,int> > adjList[10000]; // node, weight
priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq; // distance, node
int dist[10000];
memset(dist, -1, sizeof(dist));
pq.push(make_pair(0, source)); dist[0] = 0;
while(!pq.empty()){
    pair<int,int> c = pq.top();
    pq.pop();
    if(c.first != dist[c.second]) continue;
    for(auto i : adjList[c.second]){
        if(dist[i.first] == -1 || dist[i.first] > c.first + i.second){
            dist[i.first] = c.first + i.second;
            pq.push(make_pair(dist[i.first], i.first));
        }
    }
}

typedef long long ll;
ll p[V][K]; //node,kth ancestor
//DFS to compute node parents for p[i][0], first parent
bool visited[V];
ll depth[V];
void dfs(ll x){
    if (visited[x])return;
    visited[x]=true;
    for (auto i:adjlist[x]){
        if (!visited[i.first]){
            if (p[i.first][0] == -1){
                //cout<<i.first<<"<-"<<x<<endl;
                p[i.first][0] = x;
                depth[i.first] = depth[x]+1;
            }
            dfs(i.first);
        }
    }
}
void calc_k_parents(ll N){
    for (ll k=1;k<K;k++){
        for (ll i=0;i<N;i++){
            if (p[i][k-1] != -1){
                p[i][k]= p[p[i][k-1]][k-1];
            }else{p[i][k]=-1;}
           // if (k==2)cout<<i<<","<<k<<":"<<p[i][k-1]<<","<<p[p[i][k-1]][k-1]<<","<<p[i][k]<<endl;

        }
    }
}
ll find_parent(ll x,ll k){
    for (ll i=K;i>=0;i--){
        if (k>= (1<<i)){
            if (x==-1)return -1;
            x=p[x][i];
            k-=1<<i;
        }
    }
    return x;
}