Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/d1/d9a/hopcroft__karp_8cpp_source.html below:

TheAlgorithms/C++: graph/hopcroft_karp.cpp Source File

{INT_MAX};

std::vector<std::list<int> >

;

= std::vector<int>(

+ 1,NIL);

= std::vector<int>(

+ 1,NIL);

= std::vector<int>(

+ 1);

(

u = 1; u <=

; u++){

(

u = 1; u <=

; u++)

std::list<int>::iterator it;

(it =

[u].begin(); it !=

[u].end(); ++it)

(

[NIL] != INF);

std::list<int>::iterator it;

(it =

[u].begin(); it !=

[u].end(); ++it)

= std::vector<std::list<int> >(

+ 1);

[u].push_back(v);

v1a = 3, v1b = 5;

expected_res1 = 0;

assert(res1 == expected_res1);

v2a = 4, v2b = 4;

expected_res2 = 0;

assert(res2 == expected_res2);

v3a = 6, v3b = 6;

expected_res3 = 0;

assert(res3 == expected_res3);

v1 = 0, v2 = 0, e = 0;

std::cin >> v1 >> v2 >> e;

(

i = 0; i < e; ++i)

res = g.hopcroftKarpAlgorithm();

std::cout <<

<< res <<

;

constexpr int64_t INF

for assert

Represents Bipartite graph for Hopcroft Karp implementation.

std::vector< std::list< int > > adj

adj[u] stores adjacents of left side and 0 is used for dummy vertex

void addEdge(int u, int v)

function to add edge from u to v

int m

m is the number of vertices on left side of Bipartite Graph

std::vector< int > dist

dist represents the distance between vertex 'u' and vertex 'v'

int n

n is the number of vertices on right side of Bipartite Graph

bool bfs()

This function checks for the possibility of augmented path availability.

std::vector< int > pair_u

value of vertex 'u' ranges from 1 to m

std::vector< int > pair_v

value of vertex 'v' ranges from 1 to n

int hopcroftKarpAlgorithm()

This function counts the number of augmenting paths between left and right sides of the Bipartite gra...

bool dfs(int u)

This functions checks whether an augmenting path is available exists beginning with free vertex u.

HKGraph()

Default Constructor for initialization.

int main()

Main function.

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4