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