261. Graph Valid Tree

Graph Valid Tree

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Solution

public class Solution {

 public boolean validTree(int n, int[][] edges) {
        if (n < 0) return false;
        if (n <= 1) return true;
        Map<Integer, Node> map = new HashMap<>();

        for (int i = 0; i < n; i++) {
            map.put(i, new Node(i));
        }

        for (int i = 0; i < edges.length; i++) {
            int x = edges[i][0];
            int y = edges[i][1];

            Edge edge = new Edge(x, y);
            map.get(x).edges.add(edge);
            map.get(y).edges.add(edge);
        }

        boolean[] visited = new boolean[n];
        boolean[] onStack = new boolean[n];
        boolean[] result = new boolean[1];
        int[] prev = new int[n];

        dfs(map.get(0), map, visited, onStack, prev, result);

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                return false;
            }
        }

        if (result[0]) {
            return false;
        } else {
            return true;
        }
    }

    private void dfs(Node node, Map<Integer, Node> map, boolean[] visited, boolean[] onStack, int[] previous, boolean[] result) {
        if (result[0]) {
            return;
        }

        visited[node.val] = true;
        onStack[node.val] = true;

        for (Edge edge : node.edges) {
            int other = edge.other(node.val);
            if (other != -1) {
                if (!visited[other]) {
                    previous[other] = node.val;
                    dfs(map.get(other), map, visited, onStack, previous, result);
                } else if (onStack[other] && previous[node.val] != other) {
                    result[0] = true;
                    return;
                }
            }
        }

        onStack[node.val] = false;
    }


    private class Node {
        int val;
        List<Edge> edges;

        public Node(int val) {
            this.val = val;
            this.edges = new ArrayList<>();
        }
    }

    private class Edge {
        int val1;
        int val2;

        public Edge(int val1, int val2) {
            this.val1 = val1;
            this.val2 = val2;
        }

        private int other(int current) {
            if (current == val1) return val2;
            if (current == val2) return val1;
            return -1;
        }
    }


}