Saturday, January 30, 2016

EN - SPOJ (DFS) Solution - JAVA

Algorithm:

1. Find any path form source to sink (DFS/BFS). It is given that a path exists.
2. Now from the beginning node of this path,

             remove the current node from graph (set it visited).
             check if the path still exists.
             If it doesn't, the removed vertex is what you want.
             else check the same for the next node in the path until
             sink.
   
 
Source:

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

public class EN2 {  
    int maxnodes, maxedges, src, dest, edges;
    int[] top, head, prev;
    boolean marked;
    
    public void init(int maxnodes, int maxedges){
        this.maxnodes = maxnodes;
        this.maxedges = maxedges;  
        head = new int[maxedges];
        prev = new int[maxedges]; 
        top = new int[maxnodes];
        clear();
    }
    
    public void clear(){ 
        Arrays.fill(top, -1);
        edges = 0;
    } 
    
    public void addEdge(int u, int v, int capacity){
        head[edges] = v; 
        prev[edges] = top[u];
        top[u] = edges++;  
    }
    
     
    boolean dfs(int u){ 
        if(rec[u])return false;
        rec[u] = true;
         
        boolean sig=false;
        for(int e=top[u]; e>=0;e = prev[e]){
            int v = head[e];   
            from[v] = u;
            if(v==dest){from[dest] = u;return true;}
            sig = (dfs(v)==true);  
            if(sig)return sig;
        } 
        return sig;
    }
    
    int checkNodes(int u, int s, int t){  
        if(u==s)return -1; 
        int r = checkNodes(from[u], s, t);
        if(r!=-1)return r;
        Arrays.fill(rec, false);
        rec[u] = true;
        if(!dfs(s))return u;else return -1;
    }
     
    static boolean rec[];
    static int from[]; 
    public static void main(String[] args){
        int nC = IO.nextInt(); 
        
        EN2 instance = new EN2(); 
        
        //Input contains cases when m>100011. So a large value for m.
        instance.init((30011), 999999*2);
        
        while(nC-->0){  
            instance.clear(); 
            
            int n = IO.nextInt()-1;  
            
            rec = new boolean[n+1]; 
            from = new int[n+1];
            
            Arrays.fill(from, -1);
            instance.src = 0;
            instance.dest = n;
            
            int m = IO.nextInt(); 
            for(int i=0;i<m;++i){
                int a = IO.nextInt()-1;
                int b = IO.nextInt()-1; 
                instance.addEdge(a, b, 1); 
            }
            instance.dfs(0);
            int ret = instance.checkNodes(n, 0, n);
            IO.println(ret==-1?(n+1):(ret+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;
        }
        
        private static void println(Object... a){
            for(Object o:a)System.out.print(o);
            System.out.println();
        }
    }
}

No comments:

Post a Comment