16 August 2018: Depth-First Search

From UMCPC Wiki
Jump to navigation Jump to search

Friend Circles

class Solution {
    public int findCircleNum(int[][] M) {
        int circles = 0;
        boolean[] visited = new boolean[M.length];
        for (int i = 0; i < M.length; i++) {
            if (!visited[i]) {
                circles++;
                dfs(M, i, visited);
            }
        }
        return circles;
    }
    
    private void dfs(int[][] M, int i, boolean[] v) {
        if (v[i]) {
            return;
        }
        v[i] = true;
        for (int j = 0; j < M.length; j++) {
            if (M[i][j] == 1) {
                dfs(M, j, v);
            }
        }
    }
}

Flood Fill

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        if (image[sr][sc] != newColor) {
            fill(image, sr, sc, image[sr][sc], newColor);
        }
        return image;
    }
    
    private void dfs(int[][] image, int sr, int sc, int color, int newColor) {
        if (sr < 0 || sr >= image.length || sc < 0 || sc >= image[0].length || image[sr][sc] != color) {
            return;
        }
        image[sr][sc] = newColor;
        dfs(image, sr + 1, sc, color, newColor);
        dfs(image, sr - 1, sc, color, newColor);
        dfs(image, sr, sc + 1, color, newColor);
        dfs(image, sr, sc - 1, color, newColor);
    }
}

Possible Bipartition

class Solution {
    Map<Integer, List<Integer>> g = new HashMap<>();
    Map<Integer, Integer> colour = new HashMap<>();
    
    public boolean possibleBipartition(int N, int[][] dislikes) {
        for (int i = 1; i <= N; i++) {
            g.put(i, new ArrayList<>());
        }
        for (int[] edge : dislikes) {
            g.get(edge[0]).add(edge[1]);
            g.get(edge[1]).add(edge[0]);
        }
        for (int i = 1; i <= N; i++) {
            if (!colour.containsKey(i) && !dfs(i, 0)) {
                return false;
            }
        }
        return true;
    }
    
    private boolean dfs(int i, int c) {
        if (colour.containsKey(i)) {
            return colour.get(i) == c;
        }
        colour.put(i, c);
        for (int next : g.get(i)) {
            if (!dfs(next, c^1)) {
                return false;
            }
        }
        return true;
    }
}