1.) Question 2 correction. import java.util.*; public c

1.) Question 2 correction
import java.util.*;
public class MaximumFlow
{
static class Edge
{
int t, rev, cap, f;
public Edge(int t, int rev, int cap)
{
this.t = t;
this.rev = rev;
this.cap = cap;
}
}
//lets use the ArrayList data structure to create our graph
public static List<Edge>[] createGraph( int nodes)
{
List<Edge>[] graph = new List[nodes];//an array havind arraylist and os
size of provided nodes
for(int i = 0; i < nodes; i++)
{
graph[i] = new ArrayList<>();
}
return graph;
}
public static void addEdge(List<Edge>[] graph, int src, int dst, int cap)
//graph= our graph
// src = source "s";
//dst = sink "t";
//cap = capacity
{
graph[src].add(new Edge(dst, graph[dst].size(), cap));
graph[dst].add( new Edge(src, graph[src].size(), cap));
}
static boolean dinicBFS(List<Edge>[] graph, int src, int dest, int[] dist)
//dist = distance(path).
{
//by default lets alllocate distances to -1
Arrays.fill( dist, -1);
dist[src] = 0;//from itself =0

int [] q = new int[graph.length];
int sizeq = 0;
q[sizeq++] = src;
for(int i = 0; i < sizeq; i++)
{
int u = q[i];
for(Edge e : graph[u])
{
if(dist[e.t] < 0 && e.f < e.cap)
{
dist[e.t] = dist[u] + 1;
q[sizeq++] = e.t;
}
}
}
return dist[dest] >= 0;
}
static int dinicDFS(List<Edge>[] graph, int [] ptr, int [] dist,int dest,int u, int f)
{
if( u== dest)
return f;
for(;ptr[u] < graph[u].size();++ptr[u])
{
Edge e = graph[u].get(ptr[u]);
if(dist[e.t] == dist[u] + 1 && e.f < e.cap)
{
int df = dinicDFS(graph, ptr,dist,dest, e.t, Math.min(f, e.cap
- e.f) );
if(df > 0)
{
e.f += df;
graph[e.t].get(e.rev).f -= df;
return df;
}
}
}
return 0;
}
public static int maxFlow(List<Edge>[] graph, int src, int dest)
{
int flow = 0;