Collection of algorithm/source code of various algorithm

Algorithm SWE229

One Gist to collect them all!!

FordFulerson.cpp

#include <bits/stdc++.h>
using namespace std;
//[u][v] = capacity, [v][u] = flow
vector<vector<int>>rcGraph,graph;
int n;
int bfs(int s, int d, vector<int>&parent)
{
    fill(parent.begin(), parent.end(), -1);
    parent[s] = s;
    queue<pair<int,int>>q;
    q.push({s,INT_MAX});
    while(!q.empty())
    {
        int currentNode = q.front().first;
        int flow = q.front().second;
        q.pop();
        for(int nextNode: graph[currentNode])
        {
            if(parent[nextNode]==-1 && rcGraph[currentNode][nextNode] > 0)
            {
                parent[nextNode] = currentNode;
                int minFlow = min(flow, rcGraph[currentNode][nextNode]);
                if(nextNode==d)
                    return minFlow;
                q.push({nextNode, minFlow});
            }
        }
    }
    return 0;
}
int maxFlow(int source, int sink)
{
    int flow = 0;
    vector<int>parent(n);
    int bottleneckCapacity = 0;
    while(bottleneckCapacity = bfs(source, sink, parent))
    {
        flow += bottleneckCapacity;
        int currentNode = sink;
        while(currentNode != source)
        {
            int prevNode = parent[currentNode];
            rcGraph[prevNode][currentNode] -= bottleneckCapacity;
            rcGraph[currentNode][prevNode] += bottleneckCapacity;
            currentNode = prevNode;
        }
    }
    return flow;
}

int main()
{

}