Name		Name	Last commit message	Last commit date
parent directory ..
Flow		Flow
2-SAT.cpp		2-SAT.cpp
ConnectedComponnents.cpp		ConnectedComponnents.cpp
CountMinimumSpanningTree.cpp		CountMinimumSpanningTree.cpp
CountSpanningTree.cpp		CountSpanningTree.cpp
EulerianPathAndCycle.cpp		EulerianPathAndCycle.cpp
HopcroftCarp.cpp		HopcroftCarp.cpp
HungarianAlgorithm.cpp		HungarianAlgorithm.cpp
MaxFlow[Dinics-EdgeList].cpp		MaxFlow[Dinics-EdgeList].cpp
MaximumMatching.cpp		MaximumMatching.cpp
NOT_WORKING_MincostMaxflow[AdjMatrix].cpp		NOT_WORKING_MincostMaxflow[AdjMatrix].cpp
README.md		README.md
VertexCover.cpp		VertexCover.cpp

README.md

Graph

2-SAT:

1-based implementation of 2-Satisfiability Problem (positive numbers for positive propositions and negative number for negative propositions.

Connected Components

Note: Need to extract necesary code for each of the following subproblems.
StronglyConnectedComponents
BiconnectedComponents
ArticulationPointsAndBridges

Count Number of Minimum Spanning Trees

This is uses Count Number of Spanning Trees and mint

Count Number of Spanning Trees

Note: Code is equivalent to building the matrix with addEdge and finding determinant. mint is just a ModularInt with the defined operations (/, *, +, -) [note modular division needed]

Eulerian Path And Cycle

Finds an eulerian path or a cycle in O(N)

HopcroftCarp

Maximum matching O(sqrt(V)*E)

Hungarian Algorithm

Finds a weighted maximum matching in O(V^3) best for dense graphs, for non complete graphs use INF as edge cost, an alternative is to run MinCostMaxFlow.

MaxFlow

Has a running time of O(|V|^2 |E|).
Can be used to find MaximumMatching and runs relatively fast, in theory same complexity as HopcroftCarp if all edges has capacity 1.

MinCostMaxFlow

Can be a substitute of HungarianAlgorithm and also other MaxFlow with costs involved.

VertextCover

Can find a minimum vertex cover after a maximum matching is provided.
NOTE: It does not have MaxMatching you have to run MaxMatching and then pass the matching to this algorithm.