class Solution {
    public int numIslands(char[][] grid) {
        int res = 0;
        for(int i = 0;i < grid.length;i++){
            for(int j = 0;j < grid[0].length;j++){
                if(grid[i][j] == '1'){
                    res++;
                    dfs(grid,i,j);
                }
            }
        }
        return res;
    }
    public void dfs(char[][] grid,int i,int j){
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') return;
        int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
        grid[i][j] = '0';
        for(int[] dir : dirs){
            dfs(grid,i+dir[0],j+dir[1]);
        }
    }
}

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null) return root2;
        if(root2 == null) return root1;
        root1.val = root1.val+root2.val;
        root1.left= mergeTrees(root1.left,root2.left);
        root1.right = mergeTrees(root1.right,root2.right);
        return root1;
    }
}

class Solution {
    List<List<Integer>> edges;  // 保存的是边
    int[] indeg; //每个点的入度
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<List<Integer>>();
        for(int i = 0;i < numCourses;i++){
            edges.add(new ArrayList<Integer>());
        }
        indeg = new int[numCourses];
        for(int [] prerequisite:prerequisites){
            edges.get(prerequisite[1]).add(prerequisite[0]);
            indeg[prerequisite[0]]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0;i < numCourses;i++){
            if(indeg[i] == 0) q.add(i);
        }
        int visited = 0;
        while(!q.isEmpty()){
            visited++;
            int t = q.poll();
            for(int e:edges.get(t)){
                indeg[e]--;
                if(indeg[e] == 0){
                    q.add(e);
                }
            }
        }
        return visited == numCourses;
    }
}

class Solution {
    List<List<Integer>> edges;  // 保存的是边
    int visited[];
    boolean valid = true;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<List<Integer>>();
        for(int i = 0;i < numCourses;i++){
            edges.add(new ArrayList<Integer>());
        } 
        visited = new int[numCourses];
        for(int [] prerequisite:prerequisites){
            edges.get(prerequisite[1]).add(prerequisite[0]);
        }
        for(int i = 0;i < numCourses  && valid;i++){
            if(visited[i] == 0){
                dfs(i);
            }
        }
        return valid;
    }
    public void dfs(int u){
        visited[u] = 1;
        for(int t:edges.get(u)){
            if(visited[t] == 0){
                dfs(t);
                if(!valid){
                    return;
                }
            }else if(visited[t] == 1){
                valid = false;
                return;
            }
        }
        visited[u] = 2;
    }
}