int t[N];
int n, m;

int bfs(int source, int sink)

int bfs (int source, int sink)

{

	int Q[N+1], p=0,q=0;

	int Q[N + 1], p = 0, q = 0;

	bool use[N];

	memset(use, 0, sizeof(use));
	memset(t, 0, sizeof(t));
	Q[0]=source;
	use[source]=1;

	memset (use, 0, sizeof (use));
	memset (t, 0, sizeof (t));
	Q[0] = source;
	use[source] = 1;

	while(p<=q)

	while (p <= q)

	{

		int u=Q[p++];//scoatem primul element din coada

		int u = Q[p++]; //scoatem primul element din coada

		for(int i=source;i<=sink;++i) // pt fiecare nod ( adiacent )
			if(!use[i]) // nu am folosit nodul
				if(cap[u][i] - flux[u][i] > 0) // mai putem pompa?

		for (int i = source;i <= sink;++i) // pt fiecare nod ( adiacent )
			if (!use[i]) // nu am folosit nodul
				if (cap[u][i] - flux[u][i] > 0) // mai putem pompa?

				{

					Q[++q]=i; // inseram nodul i in coada
					t[i]=u;
					use[i]=1;

					Q[++q] = i; // inseram nodul i in coada
					t[i] = u;
					use[i] = 1;

				}
	}

	if(t[sink]) return 1;

	if (t[sink])
             return 1;

	return 0;
}

int edmond-karp(int source, int sink)

int edmond-karp (int source, int sink)

{

	int flow=0; //fluxul

	int flow = 0; //fluxul

	int i, min;

	while(bfs(source, sink)) // cat timp mai exista un drum de ameliorare

	while (bfs (source, sink)) // cat timp mai exista un drum de ameliorare

	{

		min=oo;
		for(i=sink; i; i=t[i])
			if(cap[t[i]][i] < min) min=cap[t[i]][i]; //calculam minimul dintre capacitatile de pe drum
 
		for(i=sink ; i; i=t[i])
			flux[t[i]][i]+=min, //adaugam minimul la fluxul de pe arcele de pe drum
			flux[i][t[i]]-=min; //scadem minimul de pe arcele inverse

		min = oo;
		for (i = sink; i; i = t[i])
			if (cap[ t[i] ][i] - flux[ t[i] ][i] < min)
                               min = cap[ t[i] ][i] - flux[ t[i] ][i];
                //calculam minimul dintre capacitatile ramase de pe drum
 
		for (i = sink ; i; i = t[i])
			flux[ t[i] ][i] += min, //adaugam minimul la fluxul de pe arcele de pe drum
			flux[i][ t[i] ] -= min; //scadem minimul de pe arcele inverse

		flow+=min; // adaugam minimul la flux

		flow += min; // adaugam minimul la flux

	}
      return flow;
}

				min=oo;

				if(cap[j][sink] < min) min=cap[j][sink];

				if(cap[j][sink]-flux[j][sink] < min) min=cap[j][sink]-flux[j][sink];

				for(i=j; i; i=t[i])

					if(cap[t[i]][i] < min) min=cap[t[i]][i]; //calculam minimul dintre capacitatile de pe drum

					if(cap[t[i]][i]-flux[t[i]][i] < min) min=cap[t[i]][i]-flux[t[i]][i];
 //calculam minimul dintre capacitatile de pe drum

				if(min == oo) continue;

Un algoritm performant pentru determinarea cuplajului maxim este Algoritmul Hopcroft-Karp. Acest algoritm în loc să determine un singur drum de ameliorare la fiecare pas, el determină un numar maximal (nu neapărat maxim) de drumuri distincte. Astfel se poate demonstra că numarul de paşi necesari este cel mult sqrt(V) . Prin urmare complexitatea va deveni O(E*sqrt(V)).

h2. Suport Minim

h2. 10. Suport Minim

Într-un graf bipartit un suport minim reprezintă o mulţime de noduri cu cardinal minim pentru care orice muchie a grafului este adiacentă cu cel puţin unul dintre nodurile mulţimii. Conform Teoremei lui Koning într-un graf bipartit cuplajul maxim şi suportul minim sunt egale.
Pentru a calcula suportul minim vom porni de la un cuplaj maxim. Nodurile din prima mulţime care aparţin cuplajului vor fi incluse în suportul minim, iar pentru cele care nu aparţin cuplajului vom folosi o funcţie recursiva care în momentul în care gaseşte o muchie care nu are cel puţin un nod în suport, adauga nodul din V2 şi şterge nodul din stânga cu care este cuplat nodul respctiv şi apelează recursiv pentru nodul din stânga.

== code(c) |

inline void support(int n)

void support(int n)

{
    vector<int>::iterator it;

	}
}

==

==
 
h2. Mulţime independentă maximală
 
Într-un graf bipartit o mulţime independentă maximală reprezintă o mulţime de noduri astfel încât oricare 2 noduri din mulţime să nu fie legate printr-o muchie iar orice muchie din graf să aiba unul din noduri în mulţimea independentă.
O proprietate interesantă a unei mulţimi independente maximale este aceea că ea este fie o clică maximală fie un subgraf complet în graful complementar.
Mulţimea independentă maximală este complementul oricărui suport minim în sensul că daca avem un suport minim, o mulţime independentă maximală va fi formată din nodurile care nu aparţin suportului minim.