## Wednesday, January 27, 2016

### IM (Intergalactic Map) SPOJ (Dinic's Algorithm - Maxflow) Solution - JAVA

Algorithm:

1. Split every vertex into a Vstart and Vend vertex.
2. Add a directed edge from Vstart to Vend with cap 1.
3. Add a source vertex X. Connect it to planet N and planet C
by directed edges of capacity 1. (Xend -> Nstart, Xend -> Cstart)
4. Every V-V edge must be connected from Vend of some vertex to Vstart
of some other with capacity 1.
5. Run Dinic's algorithm on the graph to find the max flow from
source X to sink planet T.
6. If flow is equal to 2 that means there is a path from  N to T
and a separate path from C to T.
7. Which means there is a path N-T-C. Which is what we wanted to know.
Print YES if flow==2, NO otherwise.

Source:

```import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.InputMismatchException;

/*
1. Split every vertex into a Vstart and Vend vertex.
2. Add a directed edge from Vstart to Vend with cap 1.
3. Add a source vertex X. Connect it to planet N and planet C
by directed edges of capacity 1.
4. Every V-V edge must be connected from Vend of some vertex to Vstart
of some other with capacity 1.
5. Run Dinic's algorithm on the graph to find the max flow from
source X to sink planet T.
6. If flow is equal to 2 that means there is a path from  N to T
and a separate path from C to T.
7. Which means there is a path N-T-C. Which is what we wanted to know.
Print YES if flow==2, NO otherwise.
*/

public class IM {
static final int INF = 0x7fffffff;
int maxnodes, maxedges, src, dest, edges;
int[] top, work, Q;
int[] head, prev, flow, cap, dist;
boolean marked;

public void init(int maxnodes, int maxedges){
this.maxnodes = maxnodes;
this.maxedges = maxedges;
top = new int[maxnodes];
work = new int[maxnodes];
Q = new int[maxnodes];
dist = new int[maxnodes];

prev = new int[maxedges];

flow = new int[maxedges];
cap = new int[maxedges];

clear();
}

public void clear(){
Arrays.fill(top, -1);
edges = 0;
}

public void addEdge(int u, int v, int capacity){
cap[edges] = capacity;
flow[edges] = 0;
prev[edges] = top[u];
top[u] = edges++;
}

boolean dinic_bfs(){
Arrays.fill(dist, -1);
dist[src] = 0;
int sizeQ = 0;
Q[sizeQ++] = src;
for(int i=0;i<sizeQ;++i){
int u = Q[i];
for(int e = top[u]; e>=0; e=prev[e]){
if(flow[e] < cap[e] && dist[v] < 0){
dist[v] = dist[u] + 1;
Q[sizeQ++] = v;
}
}
}
return dist[dest] >= 0;
}

int dinic_dfs(int u, int f){
if(u==dest)return f;
for(int e=work[u]; e>=0;work[u] = e = prev[e]){
if(flow[e] < cap[e] && dist[v] == dist[u]+1){
int df = dinic_dfs(v, Math.min(f, cap[e] - flow[e]));
if(df>0){
flow[e] += df;
return df;
}
}
}
return 0;
}

public int maxFlow(int src, int dest){
this.src = src;
this.dest = dest;
int flow = 0;
while(dinic_bfs()){
System.arraycopy(top, 0, work, 0, maxnodes);
while(true){
int df = dinic_dfs(src, INF);
if(df==0)break;
flow+=df;
}
}
return flow;
}

public static void main(String[] args){
int nC = IO.nextInt();

IM instance = new IM();

instance.init((30011+1)*2, 5*50011);

while(nC-->0){
instance.clear();
int n = IO.nextInt();
int m = IO.nextInt(); ```
```            /*
m should have been <=50011 as specified
by the setter, but it isn't. Add the line
written below to get a WA!.
```
```                    if(m>50011)System.out.println("Get a WA!");
That's why 5*50011 as the no. of edges above.```
`            */`
```            int N = 1, T = 2, C = 3;
int max = (n+1)*2;
for(int i=2;i<max;i+=2){
}

for(int i=0;i<m;++i){
int a = IO.nextInt();
int b = IO.nextInt();

//Test cases have incorrect vertex numbers as well.
if(a>30011 || b>30011 || a<=0 || b <=0 ) continue;

}

int flow = instance.maxFlow(1, b(T));
if(flow==2)System.out.println("YES");
else System.out.println("NO");
}
}
private static int b(int v){
return v*2;
}
private static int e(int v){
return v*2+1;
}
private static class IO {
private static InputStream stream = System.in;
private static byte[] buf = new byte;
private static int curChar, numChars;

if (numChars == -1)throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)return -1;
}
return buf[curChar++];
}

public static int nextInt() {
while (isSpaceChar(c))
int sgn = 1;
if (c == '-') {
sgn = -1;
}
int res = 0;
do {
if (c < '0' || c > '9') throw new InputMismatchException();
res *= 10;
res += c - '0';
} while (!isSpaceChar(c));
return res * sgn;
}

public static char nextChar() {