Concise and Clear DFS Solution


  • 0
    public class Solution {
        private Set<Integer> visited = new HashSet<>();
        private Map<Integer, List<Integer>> map = new HashMap<>();
        public int findCircleNum(int[][] M) {
            if (M == null || M.length == 0 || M[0].length == 0) return 0;
            int n = M.length;
            int res = 0;
            for (int i = 0; i < n; i++) {
                for (int j = i; j < n; j++) {
                    if (M[i][j] == 1) {
                        if (!map.containsKey(i)) {
                            map.put(i, new ArrayList<>());
                        }
                        if (!map.containsKey(j)) {
                            map.put(j, new ArrayList<>());
                        }
                        map.get(i).add(j);
                        map.get(j).add(i);
                    }
                }
            }
            for (int key : map.keySet()) {
                if (visited.contains(key)) continue;
                dfs(key);
                res++;
            }
            return res;
        }
        private void dfs(int curr) {
            if (!visited.add(curr)) return;
            List<Integer> neighbors = map.get(curr);
            for (int neighbor : neighbors) {
                dfs(neighbor);
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.