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];
        
        head = new int[maxedges];
        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){
        head[edges] = v;
        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]){ 
                int v = head[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]){
            int v = head[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){
                instance.addEdge(i, i+1, 1);
            }
            
            instance.addEdge(1, b(C), 1);
            instance.addEdge(1, b(N), 1);
            
            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;
                 
                
                instance.addEdge(e(a), b(b), 1);
                instance.addEdge(e(b), b(a), 1); 
            }
             
            
            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[1024];
        private static int curChar, numChars; 

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

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

        public static char nextChar() {
                int c = read();
                while (isSpaceChar(c)) c = read();
                return (char) c;
        }

        private static boolean isSpaceChar(int c) {
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
    }
}