A Graph Solution to Find Paths.

Solution.java

import java.io.*;
import java.util.*;


public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        Graph graph = new Graph(n, m);
        while (in.hasNextInt()) {
            int v1 = in.nextInt();
            int v2 = in.nextInt();
            graph.addVertice(v1);
            graph.addVertice(v2);
            graph.addEdge(v1, v2);
        }
        
        int count = 0;
        Vertice source = new Vertice(1);
        DepthFirstSearch dfs = new DepthFirstSearch(graph, source);
        //graph.printVertices();
        //graph.printMatrix();
        //for (Vertice v : graph.getVertices()) {            
        //    System.out.print("Path 1 to " + v.getValue() + ": ");
        //    for (Vertice i : dfs.pathTo(v)) {
        //       System.out.print("->" + i);
        //    }
        //    System.out.println("");
        //}        
        System.out.println(dfs.count());
    }
}

class Vertice implements Comparable<Vertice> {
        
    private int value;
    
    public Vertice(int value) {
        this.value = value;
    }
        
    public int getValue() {
        return value;     
    }
    
    @Override
    public int hashCode() {
        int prime = 7;
        return prime * value + value;
    }
    
    @Override
	public boolean equals(Object obj) {
		if (this == obj) {
			return true;
		}
		if (obj == null) {
			return false;
		}
        if (getClass() != obj.getClass()) {
			return false;
		}
        return this.value == ((Vertice)obj).value;
    }
    
    @Override
    public String toString() {
        return "V=" + value;   
    }
    
    @Override
    public int compareTo(Vertice o) {
        return this.getValue() == o.getValue() ? 0 : this.getValue() - o.getValue();   
    }
}
 
class Graph {
    
    private Set<Vertice> vertices;
    private Map<Vertice, Set<Vertice>> adjMatrix;
        
    public Graph(int n, int m) {
        this.vertices = new LinkedHashSet<>(n);
        this.adjMatrix = new HashMap<>(n);
    }
    
    public Set<Vertice> getVertices() {
        return vertices;
    }
        
    public void addVertice(int value) {
        this.vertices.add(new Vertice(value));
    }
    
    public Vertice getVertice(int value) {
        for (Vertice v : vertices) {
            if (v.getValue() == value) {
                return v;
            }
        }
        return null;
    }
        
    public void addEdge(int v1, int v2) {
        Vertice vertice1 = getVertice(v1);
        Vertice vertice2 = getVertice(v2);
        
        Set<Vertice> verticeSet = new HashSet<>(2);
        verticeSet.add(vertice1);
        
        if (adjMatrix.containsKey(vertice2)) {
            adjMatrix.get(vertice2).addAll(verticeSet);
        } else {
            adjMatrix.put(vertice2, verticeSet); 
        }        
    }
        
    public Set<Vertice> getEdges(Vertice vertice) {
        Set<Vertice> adjacents = new HashSet<>();
        if (adjMatrix.containsKey(vertice)) {
            adjacents.addAll(adjMatrix.get(vertice));
        }
        return adjacents;
    }
    
    public void printVertices() {
       System.out.println("Vertices: " + vertices);
    }
    
    public void printMatrix() {
        System.out.print("Matrix: ");
        for(Vertice v : adjMatrix.keySet()) {
            System.out.print("[" + v + "->" + String.valueOf(adjMatrix.get(v)) + "] ");
        }
        System.out.println("");
    }
}
    
class DepthFirstSearch {
        
        private final Graph graph;
        private final Vertice sourceVertice;
        private List<Vertice> visited;
        private int count = 0;
        
        public DepthFirstSearch(final Graph graph, Vertice sourceVertice) {
            this.graph = graph;
            this.sourceVertice = sourceVertice;
            this.visited = new ArrayList<>();
            dfs(graph, sourceVertice);
            //System.out.println("Visited: " + visited);
        }
        
        private int dfs(final Graph graph, Vertice vertice) {
            int verts = 0;
            visited.add(vertice);
            Set<Vertice> edges = graph.getEdges(vertice);
            for(Vertice edge : edges) {                
                if (!hasPathTo(edge)) {
                    int nodes = dfs(graph, edge);
                    if (nodes % 2 == 0) {
                        count++;
                    } else {
                        verts +=nodes;
                    } 
                }
            }
            return verts + 1;
        }
    
        public boolean hasPathTo(Vertice vertice) {
            return visited.contains(vertice);
        }

        public int count() {
            return count;
        }
    
        public List<Vertice> pathTo(Vertice vertice) {
            final List<Vertice> path = new ArrayList<>();
            if (sourceVertice.equals(vertice)) {
                path.add(sourceVertice);
                return path;
            }            
            if (hasPathTo(vertice)) {
                path.add(sourceVertice);
                for (Vertice adj : graph.getEdges(sourceVertice)) {
                    if (adj.equals(vertice)) {
                        path.add(adj);
                    } else {
                        adjacentPath(vertice, adj, path);    
                    }
                }
            }
            Collections.sort(path);
            return path;
        }
    
        private void adjacentPath(final Vertice vertice, final Vertice adj, final List<Vertice> path) {
            Set<Vertice> edges = graph.getEdges(adj);
            for (Vertice edge : edges) {
                if (edge.equals(vertice)) {
                   path.add(adj);
                   path.add(edge);
                } else {                    
                    adjacentPath(vertice, edge, path);
                    if (path.contains(vertice) && path.contains(edge)) {
                        path.add(adj);
                    }
                }
            }
        }
    }