fork download
copy 
  1. // C++ program for finding minimum cut using Ford-Fulkerson 
  2. #include <iostream> 
  3. #include <limits.h> 
  4. #include <string.h> 
  5. #include <queue> 
  6. using namespace std; 
  7.  
  8. // Number of vertices in given graph 
  9. #define V 6 
  10.  
  11. /* Returns true if there is a path from source 's' to sink 't' in 
  12. residual graph. Also fills parent[] to store the path */
  13. int bfs(int rGraph[V][V], int s, int t, int parent[]) 
  14. { 
  15. 	// Create a visited array and mark all vertices as not visited 
  16. 	bool visited[V]; 
  17. 	memset(visited, 0, sizeof(visited)); 
  18.  
  19. 	// Create a queue, enqueue source vertex and mark source vertex 
  20. 	// as visited 
  21. 	queue <int> q; 
  22. 	q.push(s); 
  23. 	visited[s] = true; 
  24. 	parent[s] = -1; 
  25.  
  26. 	// Standard BFS Loop 
  27. 	while (!q.empty()) 
  28. 	{ 
  29. 		int u = q.front(); 
  30. 		q.pop(); 
  31.  
  32. 		for (int v=0; v<V; v++) 
  33. 		{ 
  34. 			if (visited[v]==false && rGraph[u][v] > 0) 
  35. 			{ 
  36. 				q.push(v); 
  37. 				parent[v] = u; 
  38. 				visited[v] = true; 
  39. 			} 
  40. 		} 
  41. 	} 
  42.  
  43. 	// If we reached sink in BFS starting from source, then return 
  44. 	// true, else false 
  45. 	return (visited[t] == true); 
  46. } 
  47.  
  48. // A DFS based function to find all reachable vertices from s. The function 
  49. // marks visited[i] as true if i is reachable from s. The initial values in 
  50. // visited[] must be false. We can also use BFS to find reachable vertices 
  51. void dfs(int rGraph[V][V], int s, bool visited[]) 
  52. { 
  53. 	visited[s] = true; 
  54. 	for (int i = 0; i < V; i++) 
  55. 	if (rGraph[s][i] && !visited[i]) 
  56. 		dfs(rGraph, i, visited); 
  57. } 
  58.  
  59. // Prints the minimum s-t cut 
  60. void minCut(int graph[V][V], int s, int t) 
  61. { 
  62. 	int u, v; 
  63.  
  64. 	// Create a residual graph and fill the residual graph with 
  65. 	// given capacities in the original graph as residual capacities 
  66. 	// in residual graph 
  67. 	int rGraph[V][V]; // rGraph[i][j] indicates residual capacity of edge i-j 
  68. 	for (u = 0; u < V; u++) 
  69. 		for (v = 0; v < V; v++) 
  70. 			rGraph[u][v] = graph[u][v]; 
  71.  
  72. 	int parent[V]; // This array is filled by BFS and to store path 
  73.  
  74. 	// Augment the flow while there is a path from source to sink 
  75. 	while (bfs(rGraph, s, t, parent)) 
  76. 	{ 
  77. 		// Find minimum residual capacity of the edhes along the 
  78. 		// path filled by BFS. Or we can say find the maximum flow 
  79. 		// through the path found. 
  80. 		int path_flow = INT_MAX; 
  81. 		for (v=t; v!=s; v=parent[v]) 
  82. 		{ 
  83. 			u = parent[v]; 
  84. 			path_flow = min(path_flow, rGraph[u][v]); 
  85. 		} 
  86.  
  87. 		// update residual capacities of the edges and reverse edges 
  88. 		// along the path 
  89. 		for (v=t; v != s; v=parent[v]) 
  90. 		{ 
  91. 			u = parent[v]; 
  92. 			rGraph[u][v] -= path_flow; 
  93. 			rGraph[v][u] += path_flow; 
  94. 		} 
  95. 	} 
  96.  
  97. 	// Flow is maximum now, find vertices reachable from s 
  98. 	bool visited[V]; 
  99. 	memset(visited, false, sizeof(visited)); 
  100. 	dfs(rGraph, s, visited); 
  101.  
  102. 	// Print all edges that are from a reachable vertex to 
  103. 	// non-reachable vertex in the original graph 
  104. 	for (int i = 0; i < V; i++) 
  105. 	for (int j = 0; j < V; j++) 
  106. 		if (visited[i] && !visited[j] && graph[i][j]) 
  107. 			cout << i << " - " << j << endl; 
  108.  
  109. 	return; 
  110. } 
  111.  
  112. // Driver program to test above functions 
  113. int main() 
  114. { 
  115. 	// Let us create a graph shown in the above example 
  116. 	int graph[V][V] = { {0, 16, 13, 0, 0, 0}, 
  117. 						{0, 0, 10, 12, 0, 0}, 
  118. 						{0, 4, 0, 0, 14, 0}, 
  119. 						{0, 0, 9, 0, 0, 20}, 
  120. 						{0, 0, 0, 7, 0, 4}, 
  121. 						{0, 0, 0, 0, 0, 0} 
  122. 					}; 
  123.  
  124. 	minCut(graph, 0, 5); 
  125.  
  126. 	return 0; 
  127. } 
  128.  
Success #stdin #stdout 0s 4464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 - 3
4 - 3
4 - 5
https://ideone.com/1WoSUK
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!