Detects a Cycle in a graph

GraphCycleDetector.java

static class CycleDetector {

    ArrayList<ArrayList<Edge>> adj;
    boolean[] marked;
    boolean hasCycle = false;

    public CycleDetector(ArrayList<ArrayList<Edge>> adj) {
        this.adj = adj;
        marked = new boolean[adj.size()];
        for (int i = 1; i < adj.size(); i++) {
            if (!marked[i]) {
                dfs(-1, i);
            }
        }
    }

    public void dfs(int u, int v) {
        if (hasCycle) {
            return;
        }
        marked[v] = true;
        for (Edge e : adj.get(v)) {
            int w = e.otherVertex(v);
            if (!marked[w]) {
                dfs(v, w);
            } else if (w != u) {
                hasCycle = true;
            }
        }
    }
}

static class Edge implements Comparable<Edge> {

    int u;
    int v;
    int weight;

    public Edge(int u, int v, int weight) {
        this.u = u;
        this.v = v;
        this.weight = weight;
    }

    public int compareTo(Edge that) {
        return Integer.compare(this.weight, that.weight);
    }

    public int eitherVertex() {
        return u;
    }

    public int otherVertex(int x) {
        return x == v ? u : v;
    }

    public int getWeight() {
        return weight;
    }

    public String toString() {
        return "( " + u + " -- " + v + ", " + weight + " )";
    }
}