# Dinic Algorithm (2)

```#include<bits/stdc++.h>
#define ll long long

// Alternative for Dinic
// Pros: support large number of vertices and edges
// Cons: Take longer time to run.
// Usage:
//      Dinic dinic;
//      dinic.init(n);
//      maxFlow = dinic.run(source, sink);
struct Dinic2 {

struct Edge {
int v; // the other-end of this edge
ll c; // capacity
ll flow; // current flow
int rev; // index of the reverse-edge

};

int n;
int *dlevel;
pair<int, int> *prev;
int *visit;

ll maxCapacity;

Dinic2(){
maxCapacity = 1ll * oo * oo;
}

void init(int n_) {
n = n_;

dlevel = new int[n+1];
prev   = new pair<int, int> [n+1];
visit  = new int[n+1];

fill(dlevel, dlevel + n+1, 0);
fill(prev, prev + n+1, make_pair(0, 0));
fill(visit, visit + n+1, 0);
}

void addEdge(int u, int v, int w) {

}

bool constructLevel(int source, int sink) {
fill(dlevel, dlevel + n+1, -1);
dlevel[source] = 0;

queue<int> que;
que.push(source);

while(!que.empty()) {
int vertex = que.front();
que.pop();

for (int i = 0; i < adj[vertex].size(); ++i) {

if (dlevel[next] >= 0)
continue;

que.push(next);
dlevel[next] = dlevel[vertex] + 1;
}

}
}

return dlevel[sink] >= 0;
}

ll makeFlow(int source, int sink) {

ll ret = 0;

fill(visit, visit + n+1, 0);

stack<int> stk;
stk.push(source);

while(!stk.empty()) {

int now = stk.top();

if (now != sink) {

for (int i = 0; i < adj[now].size() && stk.top() == now; ++i) {

if (dlevel[next] != dlevel[now] + 1 || visit[next])
continue;

stk.push(next);
prev[next] = {now, i};
}
}

if (stk.top() == now) {
stk.pop();
visit[now] = 1;
}

}
else { // now == sink
ll f = maxCapacity, bottleneck;

for (int cur = sink; cur != source; cur = abs(prev[cur].first)) {
f = min(f, e.c - e.flow);
}

for (int cur = sink; cur != source; cur = abs(prev[cur].first)) {

e.flow += f;

e2.flow -= f;

if (e.c == e.flow)
bottleneck = prev[cur].first;
}

ret += f;

while(!stk.empty() && stk.top() != bottleneck)
stk.pop();
}

}

return ret;
}

ll run(int source, int sink) {

ll maxFlow = 0;

while (constructLevel(source, sink)) {
maxFlow += makeFlow(source, sink);
}

return maxFlow;
}
};
```