// C++ program for finding minimum cut using Ford-Fulkerson
#include <iostream>
#include <limits.h>
#include <string.h>
#include <queue>
using namespace std;
// Number of vertices in given graph
int V;
int rGraph[1000][1000];
int graph[6][6];
/* Returns true if there is a path from source 's' to sink 't' in
residual graph. Also fills parent[] to store the path */
int bfs( int s, int t, int parent[])
{
// Create a visited array and mark all vertices as not visited
bool visited[V];
memset(visited, 0, sizeof(visited));
// Create a queue, enqueue source vertex and mark source vertex
// as visited
queue <int> q;
q.push(s);
visited[s] = true;
parent[s] = -1;
// Standard BFS Loop
while (!q.empty())
{
int u = q.front();
q.pop();
for (int v=0; v<V; v++)
{
if (visited[v]==false && rGraph[u][v] > 0)
{
q.push(v);
parent[v] = u;
visited[v] = true;
}
}
}
// If we reached sink in BFS starting from source, then return
// true, else false
return (visited[t] == true);
}
// A DFS based function to find all reachable vertices from s. The function
// marks visited[i] as true if i is reachable from s. The initial values in
// visited[] must be false. We can also use BFS to find reachable vertices
void dfs( int s, bool visited[])
{
visited[s] = true;
for (int i = 0; i < V; i++)
if (rGraph[s][i] && !visited[i])
dfs( i, visited);
}
// Prints the minimum s-t cut
void minCut(int s, int t)
{
int u, v;
// Create a residual graph and fill the residual graph with
// given capacities in the original graph as residual capacities
// in residual graph
int rGraph[V][V]; // rGraph[i][j] indicates residual capacity of edge i-j
for (u = 0; u < V; u++)
for (v = 0; v < V; v++)
rGraph[u][v] = graph[u][v];
int parent[V]; // This array is filled by BFS and to store path
// Augment the flow while there is a path from source to sink
while (bfs( s, t, parent))
{
// Find minimum residual capacity of the edhes along the
// path filled by BFS. Or we can say find the maximum flow
// through the path found.
int path_flow = INT_MAX;
for (v=t; v!=s; v=parent[v])
{
u = parent[v];
path_flow = min(path_flow, rGraph[u][v]);
}
// update residual capacities of the edges and reverse edges
// along the path
for (v=t; v != s; v=parent[v])
{
u = parent[v];
rGraph[u][v] -= path_flow;
rGraph[v][u] += path_flow;
}
}
// Flow is maximum now, find vertices reachable from s
bool visited[V];
memset(visited, false, sizeof(visited));
dfs(s, visited);
int ff=0;
// Print all edges that are from a reachable vertex to
// non-reachable vertex in the original graph
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
if (visited[i] && !visited[j] && graph[i][j])
{ff++; cout << i << " - " << j << endl;}
cout<<ff;
return;
}
// Driver program to test above functions
int main()
{
V=6;
// Let us create a graph shown in the above example
int graph[V][V] = { {0, 16, 13, 0, 0, 0},
{0, 0, 10, 12, 0, 0},
{0, 4, 0, 0, 14, 0},
{0, 0, 9, 0, 0, 20},
{0, 0, 0, 7, 0, 4},
{0, 0, 0, 0, 0, 0}
};
minCut(0, 5);
return 0;
}
Ly8gQysrIHByb2dyYW0gZm9yIGZpbmRpbmcgbWluaW11bSBjdXQgdXNpbmcgRm9yZC1GdWxrZXJzb24gCiNpbmNsdWRlIDxpb3N0cmVhbT4gCiNpbmNsdWRlIDxsaW1pdHMuaD4gCiNpbmNsdWRlIDxzdHJpbmcuaD4gCiNpbmNsdWRlIDxxdWV1ZT4gCnVzaW5nIG5hbWVzcGFjZSBzdGQ7IAoKLy8gTnVtYmVyIG9mIHZlcnRpY2VzIGluIGdpdmVuIGdyYXBoIAppbnQgVjsKaW50IHJHcmFwaFsxMDAwXVsxMDAwXTsKaW50IGdyYXBoWzZdWzZdOwovKiBSZXR1cm5zIHRydWUgaWYgdGhlcmUgaXMgYSBwYXRoIGZyb20gc291cmNlICdzJyB0byBzaW5rICd0JyBpbiAKcmVzaWR1YWwgZ3JhcGguIEFsc28gZmlsbHMgcGFyZW50W10gdG8gc3RvcmUgdGhlIHBhdGggKi8KaW50IGJmcyggaW50IHMsIGludCB0LCBpbnQgcGFyZW50W10pIAp7IAoJLy8gQ3JlYXRlIGEgdmlzaXRlZCBhcnJheSBhbmQgbWFyayBhbGwgdmVydGljZXMgYXMgbm90IHZpc2l0ZWQgCglib29sIHZpc2l0ZWRbVl07IAoJbWVtc2V0KHZpc2l0ZWQsIDAsIHNpemVvZih2aXNpdGVkKSk7IAoKCS8vIENyZWF0ZSBhIHF1ZXVlLCBlbnF1ZXVlIHNvdXJjZSB2ZXJ0ZXggYW5kIG1hcmsgc291cmNlIHZlcnRleCAKCS8vIGFzIHZpc2l0ZWQgCglxdWV1ZSA8aW50PiBxOyAKCXEucHVzaChzKTsgCgl2aXNpdGVkW3NdID0gdHJ1ZTsgCglwYXJlbnRbc10gPSAtMTsgCgoJLy8gU3RhbmRhcmQgQkZTIExvb3AgCgl3aGlsZSAoIXEuZW1wdHkoKSkgCgl7IAoJCWludCB1ID0gcS5mcm9udCgpOyAKCQlxLnBvcCgpOyAKCgkJZm9yIChpbnQgdj0wOyB2PFY7IHYrKykgCgkJeyAKCQkJaWYgKHZpc2l0ZWRbdl09PWZhbHNlICYmIHJHcmFwaFt1XVt2XSA+IDApIAoJCQl7IAoJCQkJcS5wdXNoKHYpOyAKCQkJCXBhcmVudFt2XSA9IHU7IAoJCQkJdmlzaXRlZFt2XSA9IHRydWU7IAoJCQl9IAoJCX0gCgl9IAoKCS8vIElmIHdlIHJlYWNoZWQgc2luayBpbiBCRlMgc3RhcnRpbmcgZnJvbSBzb3VyY2UsIHRoZW4gcmV0dXJuIAoJLy8gdHJ1ZSwgZWxzZSBmYWxzZSAKCXJldHVybiAodmlzaXRlZFt0XSA9PSB0cnVlKTsgCn0gCgovLyBBIERGUyBiYXNlZCBmdW5jdGlvbiB0byBmaW5kIGFsbCByZWFjaGFibGUgdmVydGljZXMgZnJvbSBzLiBUaGUgZnVuY3Rpb24gCi8vIG1hcmtzIHZpc2l0ZWRbaV0gYXMgdHJ1ZSBpZiBpIGlzIHJlYWNoYWJsZSBmcm9tIHMuIFRoZSBpbml0aWFsIHZhbHVlcyBpbiAKLy8gdmlzaXRlZFtdIG11c3QgYmUgZmFsc2UuIFdlIGNhbiBhbHNvIHVzZSBCRlMgdG8gZmluZCByZWFjaGFibGUgdmVydGljZXMgCnZvaWQgZGZzKCBpbnQgcywgYm9vbCB2aXNpdGVkW10pIAp7IAoJdmlzaXRlZFtzXSA9IHRydWU7IAoJZm9yIChpbnQgaSA9IDA7IGkgPCBWOyBpKyspIAoJaWYgKHJHcmFwaFtzXVtpXSAmJiAhdmlzaXRlZFtpXSkgCgkJZGZzKCBpLCB2aXNpdGVkKTsgCn0gCgovLyBQcmludHMgdGhlIG1pbmltdW0gcy10IGN1dCAKdm9pZCBtaW5DdXQoaW50IHMsIGludCB0KSAKeyAKCWludCB1LCB2OyAKCgkvLyBDcmVhdGUgYSByZXNpZHVhbCBncmFwaCBhbmQgZmlsbCB0aGUgcmVzaWR1YWwgZ3JhcGggd2l0aCAKCS8vIGdpdmVuIGNhcGFjaXRpZXMgaW4gdGhlIG9yaWdpbmFsIGdyYXBoIGFzIHJlc2lkdWFsIGNhcGFjaXRpZXMgCgkvLyBpbiByZXNpZHVhbCBncmFwaCAKCWludCByR3JhcGhbVl1bVl07IC8vIHJHcmFwaFtpXVtqXSBpbmRpY2F0ZXMgcmVzaWR1YWwgY2FwYWNpdHkgb2YgZWRnZSBpLWogCglmb3IgKHUgPSAwOyB1IDwgVjsgdSsrKSAKCQlmb3IgKHYgPSAwOyB2IDwgVjsgdisrKSAKCQkJckdyYXBoW3VdW3ZdID0gZ3JhcGhbdV1bdl07IAoKCWludCBwYXJlbnRbVl07IC8vIFRoaXMgYXJyYXkgaXMgZmlsbGVkIGJ5IEJGUyBhbmQgdG8gc3RvcmUgcGF0aCAKCgkvLyBBdWdtZW50IHRoZSBmbG93IHdoaWxlIHRoZXJlIGlzIGEgcGF0aCBmcm9tIHNvdXJjZSB0byBzaW5rIAoJd2hpbGUgKGJmcyggcywgdCwgcGFyZW50KSkgCgl7IAoJCS8vIEZpbmQgbWluaW11bSByZXNpZHVhbCBjYXBhY2l0eSBvZiB0aGUgZWRoZXMgYWxvbmcgdGhlIAoJCS8vIHBhdGggZmlsbGVkIGJ5IEJGUy4gT3Igd2UgY2FuIHNheSBmaW5kIHRoZSBtYXhpbXVtIGZsb3cgCgkJLy8gdGhyb3VnaCB0aGUgcGF0aCBmb3VuZC4gCgkJaW50IHBhdGhfZmxvdyA9IElOVF9NQVg7IAoJCWZvciAodj10OyB2IT1zOyB2PXBhcmVudFt2XSkgCgkJeyAKCQkJdSA9IHBhcmVudFt2XTsgCgkJCXBhdGhfZmxvdyA9IG1pbihwYXRoX2Zsb3csIHJHcmFwaFt1XVt2XSk7IAoJCX0gCgoJCS8vIHVwZGF0ZSByZXNpZHVhbCBjYXBhY2l0aWVzIG9mIHRoZSBlZGdlcyBhbmQgcmV2ZXJzZSBlZGdlcyAKCQkvLyBhbG9uZyB0aGUgcGF0aCAKCQlmb3IgKHY9dDsgdiAhPSBzOyB2PXBhcmVudFt2XSkgCgkJeyAKCQkJdSA9IHBhcmVudFt2XTsgCgkJCXJHcmFwaFt1XVt2XSAtPSBwYXRoX2Zsb3c7IAoJCQlyR3JhcGhbdl1bdV0gKz0gcGF0aF9mbG93OyAKCQl9IAoJfSAKCgkvLyBGbG93IGlzIG1heGltdW0gbm93LCBmaW5kIHZlcnRpY2VzIHJlYWNoYWJsZSBmcm9tIHMgCglib29sIHZpc2l0ZWRbVl07IAoJbWVtc2V0KHZpc2l0ZWQsIGZhbHNlLCBzaXplb2YodmlzaXRlZCkpOyAKCWRmcyhzLCB2aXNpdGVkKTsgCiAgaW50IGZmPTA7CgkvLyBQcmludCBhbGwgZWRnZXMgdGhhdCBhcmUgZnJvbSBhIHJlYWNoYWJsZSB2ZXJ0ZXggdG8gCgkvLyBub24tcmVhY2hhYmxlIHZlcnRleCBpbiB0aGUgb3JpZ2luYWwgZ3JhcGggCglmb3IgKGludCBpID0gMDsgaSA8IFY7IGkrKykgCglmb3IgKGludCBqID0gMDsgaiA8IFY7IGorKykgCgkJaWYgKHZpc2l0ZWRbaV0gJiYgIXZpc2l0ZWRbal0gJiYgZ3JhcGhbaV1bal0pIAoJCXtmZisrOwljb3V0IDw8IGkgPDwgIiAtICIgPDwgaiA8PCBlbmRsO30KCQljb3V0PDxmZjsKCglyZXR1cm47IAp9IAoKLy8gRHJpdmVyIHByb2dyYW0gdG8gdGVzdCBhYm92ZSBmdW5jdGlvbnMgCmludCBtYWluKCkgCnsKCVY9NjsKCS8vIExldCB1cyBjcmVhdGUgYSBncmFwaCBzaG93biBpbiB0aGUgYWJvdmUgZXhhbXBsZSAKCWludCBncmFwaFtWXVtWXSA9IHsgezAsIDE2LCAxMywgMCwgMCwgMH0sIAoJCQkJCQl7MCwgMCwgMTAsIDEyLCAwLCAwfSwgCgkJCQkJCXswLCA0LCAwLCAwLCAxNCwgMH0sIAoJCQkJCQl7MCwgMCwgOSwgMCwgMCwgMjB9LCAKCQkJCQkJezAsIDAsIDAsIDcsIDAsIDR9LCAKCQkJCQkJezAsIDAsIDAsIDAsIDAsIDB9IAoJCQkJCX07IAoKCW1pbkN1dCgwLCA1KTsgCgoJcmV0dXJuIDA7IAp9IAo=