BFS(2)

BFS选编（2）

733. Flood Fill

public int[][] floodFill(int[][] image, int sr, int sc, int color) {
    Deque<int[]> q=new LinkedList<>();
    int row=image.length;
    int col=image[0].length;
    int c=image[sr][sc];
    int[] dx={1,-1,0,0};
    int[] dy={0,0,1,-1};
    q.offer(new int[]{sr,sc});
    while(!q.isEmpty()){
        int[] cur=q.poll();
        int i=cur[0];
        int j=cur[1];
        if(image[i][j]!=color){
            image[i][j]=color;
            for (int k = 0; k < 4; k++) {
                int x=i+dx[k];
                int y=j+dy[k];
                if(x>=0 && x<row && y>=0 && y<col
                        && image[x][y]==c){
                    q.offer(new int[]{x,y});
                }
            }
        }
    }
    return image;
}

743. Network Delay Time

//dijkstra
public int networkDelayTime(int[][] times, int n, int k) {
    Map<Integer,List<int[]>> map=new HashMap<>();
    for (int[] time : times) {
        int from=time[0];
        int to=time[1];
        int len=time[2];
        map.putIfAbsent(from,new ArrayList<>());
        map.get(from).add(new int[]{to,len});
    }
    int[] dist=new int[n+1];
    Arrays.fill(dist,Integer.MAX_VALUE);
    dist[k]=0;
    PriorityQueue<int[]> q=new PriorityQueue<>((a,b)->(a[1]-b[1]));
    q.offer(new int[]{k,0});
    while(!q.isEmpty()){
        int[] cur=q.poll();
        int vertex=cur[0];
        int distToStart=cur[1];
        if(map.containsKey(vertex)){
            for (int[] ints : map.get(vertex)) {
                int next=ints[0];
                int len=ints[1];
                if(distToStart+len<dist[next]){
                    dist[next]=distToStart+len;
                    q.offer(new int[]{next,distToStart+len});
                }
            }
        }
    }
    int res=Integer.MIN_VALUE;
    for (int i = 1; i < n; i++) {
        if(dist[i]==Integer.MAX_VALUE){
            return -1;
        }
        res=Math.max(res,dist[i]);
    }
    return res;
}

752. Open the Lock

KEY ISSUE: how to represent changes of layer?

public int openLock(String[] deadends, String target) {
    Set<String> dead=new HashSet<>();
    for (String deadend : deadends) {
        dead.add(deadend);
    }
    Deque<String> q=new LinkedList<>();
    Set<String> visited=new HashSet<>();
    visited.add("0000");
    q.offer("0000");
    q.offer(null);
    int depth=0;
    while(!q.isEmpty()){
        String cur=q.poll();
        if(!dead.contains(cur)){
            if(cur==null){
                depth++;
                if(!q.isEmpty()){
                    q.offer(null);
                }
            }else if(cur.equals(target)){
                return depth;
            }else{
                for (int i = 0; i < 4; i++) {
                    for(int d=-1; d<=1; d+=2){
                        StringBuilder sb=new StringBuilder();
                        for (int p = 0; p <= i-1; p++) {
                            sb.append(cur.charAt(p));
                        }
                        char c=cur.charAt(i);
                        char next=(char)(c+d);
                        if(next>'9'){
                            next='0';
                        }
                        if(next<'0'){
                            next='9';
                        }
                        sb.append(next);
                        for (int p = i+1; p < 4; p++) {
                            sb.append(cur.charAt(p));
                        }
                        String string=sb.toString();
                        if(!visited.contains(string)){
                            visited.add(string);
                            q.offer(string);
                        }
                    }
                }
            }
        }
    }
    return -1;
}

773. Sliding Puzzle

KEY ISSUE: how to represent changes of layer?

int[][] neighbors={
        {1,3},
        {0,2,4},
        {1,5},
        {0,4},
        {1,3,5},
        {2,4}
};
public int slidingPuzzle(int[][] board) {
    Set<String> seen=new HashSet<>();
    Deque<String> q=new LinkedList<>();
    char[] chars=new char[6];
    chars[0]=(char)(board[0][0]+'0');
    chars[1]=(char)(board[0][1]+'0');
    chars[2]=(char)(board[0][2]+'0');
    chars[3]=(char)(board[1][0]+'0');
    chars[4]=(char)(board[1][1]+'0');
    chars[5]=(char)(board[1][2]+'0');
    q.offer(new String(chars));
    q.offer(null);
    seen.add(new String(chars));
    int depth=0;
    while(!q.isEmpty()){
        String cur=q.poll();
        if(cur==null){
            depth++;
            if(!q.isEmpty()){
                q.offer(null);
            }
        }else if(cur.equals("123450")){
            return depth;
        }else{
            int index=cur.indexOf("0");
            for (int i : neighbors[index]) {
                String next=swap(cur,index,i);
                if(!seen.contains(next)){
                    seen.add(next);
                    q.offer(next);
                }
            }
        }
    }
    return -1;
}

String swap(String cur, int index, int i){
    char[] chars=cur.toCharArray();
    char temp=chars[index];
    chars[index]=chars[i];
    chars[i]=temp;
    return new String(chars);
}

785. Is Graph Bipartite?

BFS Solution:

class Solution {
    public boolean isBipartite(int[][] graph) {
        int len = graph.length;
        int[] colors = new int[len];
        
        for (int i = 0; i < len; i++) {
            if (colors[i] != 0) continue;
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(i);
            colors[i] = 1;   // Blue: 1; Red: -1.
            
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                for (int next : graph[cur]) {
                    if (colors[next] == 0) {          // If this node hasn't been colored;
                        colors[next] = -colors[cur];  // Color it with a different color;
                        queue.offer(next);
                    } else if (colors[next] != -colors[cur]) {   // If it is colored and its color is different, return false;
                        return false;
                    }
                }
            }
        }
        
        return true;
    }
}

802. Find Eventual Safe States

//if except to safe nodes, out degree == 0
//then is safe node
public List<Integer> eventualSafeNodes(int[][] graph) {
    int n=graph.length;
    List<Integer> res=new LinkedList<>();
    Map<Integer,List<Integer>> map=new HashMap<>();
    int[] outs=new int[n];
    for (int i = 0; i < graph.length; i++) {
        if(graph[i].length==0){
            res.add(i);
        }else{
            outs[i]=graph[i].length;
            for (int next : graph[i]) {
                map.putIfAbsent(next,new ArrayList<>());
                map.get(next).add(i);
            }
        }
    }


    Deque<Integer> q=new LinkedList<>();
    for (Integer node : res) {
        q.offer(node);
    }
    while(!q.isEmpty()){
        int cur=q.poll();
        if(map.containsKey(cur)){
            for (Integer from : map.get(cur)) {
                outs[from]--;
                if(outs[from]==0){
                    q.offer(from);
                    res.add(from);
                }
            }
        }

    }
    Collections.sort(res);
    return res;
}

787. Cheapest Flights Within K Stops

class State{
    int index;
    int distToSrc;
    int nodeToSrc;
    State(int i, int distToSrc, int nodeToSrc){
        this.index=i;
        this.distToSrc=distToSrc;
        this.nodeToSrc=nodeToSrc;
    }
}

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    List<int[]>[] graph=new List[n];
    for (int i = 0; i < n; i++) {
        graph[i]=new ArrayList<>();
    }
    for (int[] flight : flights) {
        int from=flight[0];
        int to=flight[1];
        int cost=flight[2];
        graph[from].add(new int[]{to,cost});
    }
    k++;
    int[] distTo=new int[n];
    int[] nodeTo=new int[n];
    Arrays.fill(distTo,Integer.MAX_VALUE);
    Arrays.fill(nodeTo,Integer.MAX_VALUE);
    distTo[src]=0;
    nodeTo[src]=0;
    PriorityQueue<State> pq=new PriorityQueue<>((a,b)->(a.distToSrc-b.distToSrc));
    pq.offer(new State(src,0,0));
    while(!pq.isEmpty()){
        State curNode=pq.poll();
        int cur= curNode.index;
        int curDistToSrc=curNode.distToSrc;
        int curNodeToSrc=curNode.nodeToSrc;

        if(cur==dst){
            return curDistToSrc;
        }
        if(curNodeToSrc+1>k){
            continue;
        }
        for (int[] ints : graph[cur]) {
            int next=ints[0];
            int costToNext=curDistToSrc+ints[1];
            int nodeToNext=curNodeToSrc+1;
            if(costToNext<distTo[next]){
                distTo[next]=costToNext;
                nodeTo[next]=nodeToNext;
            }
            if(costToNext>distTo[next] && nodeToNext>nodeTo[next]){
                continue;
            }
            pq.offer(new State(next,costToNext,nodeToNext));
        }
    }
    return -1;
}

994. Rotting Oranges

public int orangesRotting(int[][] grid) {
    int row=grid.length;
    int col=grid[0].length;
    int count=0;
    int[] dx=new int[]{1,-1,0,0};
    int[] dy=new int[]{0,0,1,-1};
    Deque<int[]> q=new LinkedList<>();
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if(grid[i][j]==1){
                count++;
            }else if(grid[i][j]==2){
                q.offer(new int[]{i,j});
            }
        }
    }
    int minute=0;
    while(!q.isEmpty()){
        int size=q.size();
        while(size-->0){
            int[] cur=q.poll();
            int i=cur[0];
            int j=cur[1];
            for (int k = 0; k < 4; k++) {
                int x=i+dx[k];
                int y=j+dy[k];
                if(x<0 || x>=row || y<0 || y>=col || grid[x][y]!=1){
                    continue;
                }
                grid[x][y]=2;
                count--;
                q.offer(new int[]{x,y});
            }
        }
        if(!q.isEmpty()){
            minute++;
        }
    }
    return count==0 ? minute : -1;
}

934. Shortest Bridge

public int shortestBridge(int[][] grid) {
    int row=grid.length;
    int col=grid[0].length;
    int[] dx=new int[]{0,0,1,-1};
    int[] dy=new int[]{1,-1,0,0};
    a:for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if(grid[i][j]==1){
                set(grid,i,j,row,col);
                break a;
            }
        }
    }
    Deque<int[]> q=new LinkedList<>();
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if(grid[i][j]==2){
                q.offer(new int[]{i,j});
            }
        }
    }
    int depth=0;
    while(!q.isEmpty()){
        int size=q.size();
        while(size-->0){
            int[] cur=q.poll();
            int i=cur[0];
            int j=cur[1];
            for (int k = 0; k < 4; k++) {
                int x=i+dx[k];
                int y=j+dy[k];
                if(x<0 || x>=row || y<0 || y>=col || grid[x][y]==2){
                    continue;
                }
                if(grid[x][y]==1){
                    return depth;
                }
                q.offer(new int[]{x,y});
                grid[x][y]=2;
            }
        }
        depth++;
    }
    return 0;
}

void set(int[][] grid, int i, int j, int row, int col){
    if(i<0 || i>=row || j<0 || j>=col || grid[i][j]!=1){
        return;
    }
    grid[i][j]=2;
    set(grid,i+1,j,row,col);
    set(grid,i-1,j,row,col);
    set(grid,i,j+1,row,col);
    set(grid,i,j-1,row,col);
}

2503. Maximum Number of Points From Grid Queries

好题：

• dfs + memo 超时 （17/21）

int row;
int col;
public int[] maxPoints(int[][] grid, int[] queries) {
    Map<Integer,Integer> memo=new HashMap<>();
    int k=queries.length;
    int[] res=new int[k];
    row=grid.length;
     col=grid[0].length;
    for (int i = 0; i < k; i++) {
        int query=queries[i];
        if(memo.containsKey(query)){
            res[i]=memo.get(query);
        }else{
            int point=dfs(grid,query,new boolean[row][col],0,0);
            memo.put(query,point);
            res[i]=point;
        }
    }
    return res;
}

int dfs(int[][] grid, int query, boolean[][] visited, int i, int j){
    if(i<0 || i>=row || j<0 || j>=col || grid[i][j]>=query || visited[i][j]){
        return 0;
    }
    visited[i][j]=true;
    return 1+dfs(grid,query,visited,i+1,j)
            +dfs(grid,query,visited,i-1,j)
            +dfs(grid,query,visited,i,j+1)
            +dfs(grid,query,visited,i,j-1);
}

• priorityqueue + bfs
  • 直接利用原数组去重，若值为0则跳过
  • 注意：在点入队时去重，而不是访问时才去重，防止重复入队，导致重复计数！

public int[] maxPoints(int[][] grid, int[] queries) {
    int row=grid.length;
    int col=grid[0].length;
    int[] dx=new int[]{0,0,1,-1};
    int[] dy=new int[]{1,-1,0,0};
    int n=queries.length;

    PriorityQueue<int[]> queryQueue=new PriorityQueue<>((a,b)->(a[1]-b[1]));
    for (int i = 0; i < n; i++) {
        queryQueue.offer(new int[]{i,queries[i]});
    }

    PriorityQueue<int[]> bfsQueue=new PriorityQueue<>((a,b)->(a[2]-b[2]));
    bfsQueue.offer(new int[]{0,0,grid[0][0]});
    grid[0][0]=0;
    int[] res=new int[n];
    int reach=0;
    while(!queryQueue.isEmpty()){
        int[] curQuery=queryQueue.poll();
        int idx=curQuery[0];
        int query=curQuery[1];
        while(!bfsQueue.isEmpty() && bfsQueue.peek()[2]<query){
            int[] node=bfsQueue.poll();
            reach++;
            int i=node[0];
            int j=node[1];
            for (int k = 0; k < 4; k++) {
                int x=i+dx[k];
                int y=j+dy[k];
                if(x<0 || x>=row || y<0 || y>=col || grid[x][y]==0){
                    continue;
                }
                bfsQueue.offer(new int[]{x,y,grid[x][y]});
                grid[x][y]=0;   //set to 0, to avoid repetition
            }
        }
        res[idx]=reach;
    }
    return res;
}

886. Possible Bipartition

public boolean possibleBipartition(int n, int[][] dislikes) {
    List<Integer>[] graph=new List[n+1];
    for (int[] dislike : dislikes) {
        int a=dislike[0];
        int b=dislike[1];
        if(graph[a]==null){
            graph[a]=new ArrayList<>();
        }
        graph[a].add(b);
        if(graph[b]==null){
            graph[b]=new ArrayList<>();
        }
        graph[b].add(a);
    }
    Deque<Integer> q=new LinkedList<>();
    int[] party=new int[n+1];
    for (int i = 1; i <= n; i++) {
        if(party[i]!=0){
            continue;
        }
        party[i]=1;
        q.offer(i);
        while(!q.isEmpty()){
            int cur=q.poll();
            int curParty=party[cur];
            if(graph[cur]!=null){
                for (int next : graph[cur]) {
                    if(party[next]==curParty){
                        return false;
                    }
                    if(party[next]==0){
                        party[next]=-curParty;
                        q.offer(next);
                    }
                }
            }
        }
    }
    return true;
}

1034. Coloring A Border

注意：根据初始时刻判断，要等所有判断结束后方可变色

public int[][] colorBorder(int[][] grid, int row, int col, int color) {
    int ro=grid.length;
    int co=grid[0].length;
    int[] dx=new int[]{1,-1,0,0};
    int[] dy=new int[]{0,0,1,-1};
    Deque<int[]> q=new LinkedList<>();
    q.offer(new int[]{row,col});
    int tag=grid[row][col];
    boolean[][] visited=new boolean[ro][co];
    boolean[][] change=new boolean[ro][co];
    visited[row][col]=true;
    while(!q.isEmpty()){
        int[] cur=q.poll();
        int i=cur[0];
        int j=cur[1];
        boolean isBoarder=false;
        for (int k = 0; k < 4; k++) {
            int x=i+dx[k];
            int y=j+dy[k];
            if(x>=0 && x<ro && y>=0 && y<co){
                if(grid[x][y]!=tag){
                    isBoarder=true;
                }
                if(grid[x][y]==tag && !visited[x][y]){
                    visited[x][y]=true;
                    q.offer(new int[]{x,y});
                }
            }
        }
        if(isBoarder || i==0 || i==ro-1 || j==0 || j==co-1){
            change[i][j]=true;
        }
    }
    for (int i = 0; i < ro; i++) {
        for (int j = 0; j < co; j++) {
            if(change[i][j]){
                grid[i][j]=color;
            }
        }
    }
    return grid;
}

1162. As Far from Land as Possible

public int maxDistance(int[][] grid) {
    int n=grid.length;
    Deque<int[]> q=new LinkedList<>();
    int[] dx=new int[]{0,0,1,-1};
    int[] dy=new int[]{1,-1,0,0};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if(grid[i][j]==1){
                q.offer(new int[]{i,j});
            }
        }
    }
    if(q.size()==0 || q.size()==n*n){
        return -1;
    }
    int depth=0;
    while(!q.isEmpty()){
        int size=q.size();
        while(size-->0){
            int[] cur=q.poll();
            int i=cur[0];
            int j=cur[1];
            for (int k = 0; k < 4; k++) {
                int x=i+dx[k];
                int y=j+dy[k];
                if(x<0 || x>=n || y<0 || y>=n || grid[x][y]==1){
                    continue;
                }
                q.offer(new int[]{x,y});
                grid[x][y]=1;
            }
        }
        if(!q.isEmpty()){
            depth++;
        }
    }
    return depth;
}

126. Word Ladder II

public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
    Set<String> set=new HashSet<>(wordList);
    set.add(beginWord);
    Map<String,Set<String>> neighbors=new HashMap<>();
    for (String word : set) {
        char[] chars = word.toCharArray();
        neighbors.put(word,new HashSet<>());
        for (int i = 0; i < word.length(); i++) {
            char c=chars[i];
            for(char j='a'; j<='z'; j++){
                if(j==c){
                    continue;
                }
                chars[i]=j;
                String s=new String(chars);
                if(set.contains(s)){
                    neighbors.get(word).add(s);
                }
            }
            chars[i]=c;
        }
    }
    List<List<String>> layers=new ArrayList<>();
    Deque<String> q=new LinkedList<>();
    q.offer(beginWord);
    set.remove(beginWord); //once in queue, removed from set
    boolean reached=false;
    a:while(!q.isEmpty()){
        int size=q.size();
        List<String> curLayer=new ArrayList<>();
        while(size-->0){
            String cur=q.poll();
            if(cur.equals(endWord)){
                reached=true;
                break a;
            }
            curLayer.add(cur);
            for (String next : neighbors.get(cur)) {
                if(set.contains(next)){
                    q.offer(next);
                    set.remove(next);
                }
            }
        }
        layers.add(curLayer);
    }
    if(!reached){
        return new ArrayList<>();
    }
    List<List<String>> paths=new ArrayList<>();
    LinkedList<String> path=new LinkedList<>();
    path.add(endWord);
    paths.add(path);
    for (int i = layers.size() - 1; i >= 0; i--) {
        List<List<String>> modified=new ArrayList<>();
        List<String> curLayer=layers.get(i);
        for (List<String> list : paths) {
            String end=list.get(0);
            for (String s : curLayer) {
                if(neighbors.get(end).contains(s)){
                    LinkedList<String> l=new LinkedList<>(list);
                    l.addFirst(s);
                    modified.add(l);
                }
            }
        }
        paths=modified;
    }
    return paths;
}

818. Race Car

https://leetcode.com/problems/race-car/discuss/124326/Summary-of-the-BFS-and-DP-solutions-with-intuitive-explanation

BFS

public int racecar(int target) {
    Set<String> set=new HashSet<>();
    PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->(a[2]-b[2]));
    //curId, curSpeed, curStep
    pq.offer(new int[]{0,1,0});
    while(!pq.isEmpty()){
        int[] cur=pq.poll();
        int curId=cur[0];
        int curSpeed=cur[1];
        int curStep=cur[2];
        if(curId==target){
            return curStep;
        }
        int nextStep=curStep+1;
        //accelerate
        int nextId=curId+curSpeed;
        int nextSpeed=curSpeed*2;
        String s=nextId+","+nextSpeed;
        if(nextId>=0 && nextSpeed<=2*target &&!set.contains(s)){
            set.add(s);
            pq.offer(new int[]{nextId,nextSpeed,nextStep});
        }
        //reverse
        nextSpeed=curSpeed>0 ? -1 : 1;
        nextId=curId;
        s=nextId+","+nextSpeed;
        if(!set.contains(s)){
            set.add(s);
            pq.offer(new int[]{nextId,nextSpeed,nextStep});
        }

    }
    return -1;
}

DP

296. Best Meeting Point

BFS

56/58

int row;
int col;
int[][] grid;
int[] dx=new int[]{0,0,1,-1};
int[] dy=new int[]{1,-1,0,0};
int[][] dist;
public int minTotalDistance(int[][] grid) {
    this.grid=grid;
    row=grid.length;
    col=grid[0].length;

    dist=new int[row][col];
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if(grid[i][j]==1){
                bfs(i,j);
            }
        }
    }
    int min=Integer.MAX_VALUE;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            min=Math.min(min,dist[i][j]);
        }
    }
    return min;
}

private void bfs(int r, int c){
    boolean[][] visited=new boolean[row][col];
    Deque<int[]> q=new LinkedList<>();
    q.offer(new int[]{r,c});
    visited[r][c]=true;
    int d=0;
    while(!q.isEmpty()){
        int size=q.size();
        while(size-->0){
            int[] cur=q.poll();
            int i=cur[0];
            int j=cur[1];
            dist[i][j]+=d;
            int x,y;
            for (int k = 0; k < 4; k++) {
                x=i+dx[k];
                y=j+dy[k];
                if(x<0 || x>=row || y<0 || y>=col || visited[x][y]){
                    continue;
                }
                q.offer(new int[]{x,y});
                visited[x][y]=true;
            }
        }
        d++;
    }
}

找中点

public int minTotalDistance(int[][] grid) {
    List<Integer> list1=new ArrayList<>();
    List<Integer> list2=new ArrayList<>();
    int row=grid.length;
    int col=grid[0].length;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if(grid[i][j]==1){
                list1.add(i);
                list2.add(j);
            }
        }
    }
    return dist(list1)+dist(list2);
}

private int dist(List<Integer> list){
    Collections.sort(list);
    int mid=list.get(list.size()/2);
    int res=0;
    for (Integer num : list) {
        res+=Math.abs(mid-num);
    }
    return res;
}

1197. Minimum Knight Moves

注意更新逻辑：

• 当前dist > 最短距离，则跳过当前状态
• 入队时同时更新最短距离

public int minKnightMoves(int x, int y) {
    int[][] dist=new int[601][601]; //[-300,300]
    for (int[] arr : dist) {
        Arrays.fill(arr,Integer.MAX_VALUE);
    }
    //x+300,y+300
    int[][] dirs=new int[][]{{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-1,2},{-2,1}};
    PriorityQueue<int[]> q=new PriorityQueue<>((a,b)->(a[2]-b[2]));
    q.offer(new int[]{300,300,0});
    while(!q.isEmpty()){
        int[] cur=q.poll();
        int i=cur[0];
        int j=cur[1];
        int d=cur[2];
        if(d>dist[i][j]){
            continue;
        }
        if(i==x+300 && j==y+300){
            return d;
        }
        dist[i][j]=d;
        for (int[] dir : dirs) {
            int nx=i+dir[0];
            int ny=j+dir[1];
            if(nx>=0 && nx<=600 && ny>=0 && ny<=600 && d+1<dist[nx][ny]){
                dist[nx][ny]=d+1;
                q.offer(new int[]{nx,ny,d+1});
            }
        }
    }
    return -1;
}

1245. Tree Diameter

思路：

1. Start at any node A and traverse the tree to find the furthest node from it, let’s call it B.
2. Having found the furthest node B, traverse the tree from B to find the furthest node from it, lets call it C.
3. The distance between B and C is the tree diameter.

public class LeetCode1245 {
    int n;
    List<Integer>[] graph;
    public int treeDiameter(int[][] edges) {
        n=edges.length;
        graph=new List[n+1];//[0,n]
        for (int i = 0; i <= n; i++) {
            graph[i]=new ArrayList<>();
        }
        for (int[] edge : edges) {
            int a=edge[0];
            int b=edge[1];
            graph[a].add(b);
            graph[b].add(a);
        }
        int[] arr=bfs(0);
        int a=arr[0];   //one of the farthest nodes
        return bfs(a)[1];
    }

    //find the farthest node and distance
    int[] bfs(int start){
        boolean[] visited=new boolean[n+1];
        Deque<Integer> q=new LinkedList<>();
        q.offer(start);
        visited[start]=true;
        int d=0;
        int cur=0;
        while(!q.isEmpty()){
            int size=q.size();
            while(size-->0){
                cur=q.poll();
                for (Integer next : graph[cur]) {
                    if(!visited[next]){
                        q.offer(next);
                        visited[next]=true;
                    }
                }
            }
            if(!q.isEmpty()){
                d++;
            }
        }
        return new int[]{cur,d};
    }
}

1490. Clone N-ary Tree

public Node cloneTree(Node root) {
    if(root==null){
        return null;
    }
    Map<Node,Node> map=new HashMap<>();
    Deque<Node> q=new LinkedList<>();
    q.offer(root);
    map.put(root,new Node(root.val));
    while(!q.isEmpty()){
        Node cur=q.poll();
        Node copy=map.get(cur);
        for (Node child : cur.children) {
            q.offer(child);
            Node nextcopy=new Node(child.val);
            map.put(child,nextcopy);
            copy.children.add(nextcopy);
        }
    }
    return map.get(root);
}

1466. Reorder Routes to Make All Paths Lead to the City Zero

public int minReorder(int n, int[][] connections) {
    List<Integer>[] graphFrom=new List[n];
    List<Integer>[] graphTo=new List[n];
    for (int i = 0; i < n; i++) {
        graphFrom[i]=new ArrayList<>();
        graphTo[i]=new ArrayList<>();
    }
    for (int[] connection : connections) {
        int from=connection[0];
        int to=connection[1];
        graphFrom[to].add(from);
        graphTo[from].add(to);
    }
    Deque<Integer> q=new LinkedList<>();
    boolean[] visited=new boolean[n];
    visited[0]=true;
    q.offer(0);
    int res=0;
    while(!q.isEmpty()){
        int cur=q.poll();
        for (Integer from : graphFrom[cur]) {
            if(!visited[from]){
                q.offer(from);
                visited[from]=true;
            }
        }
        for (Integer to : graphTo[cur]) {
            if(!visited[to]){
                res++;
                q.offer(to);
                visited[to]=true;
            }
        }
    }
    return res;
}

2737. Find the Closest Marked Node

public int minimumDistance(int n, List<List<Integer>> edges, int s, int[] marked) {
    Map<Integer,Integer>[] maps=new Map[n];
    for (int i = 0; i < n; i++) {
        maps[i]=new HashMap<>();
    }
    for (List<Integer> edge : edges) {
        int from=edge.get(0);
        int to=edge.get(1);
        int w=edge.get(2);
        if(!maps[from].containsKey(to) || maps[from].get(to)>w){
            maps[from].put(to,w);
        }
    }
    HashSet<Integer> target=new HashSet<>();
    for (int i : marked) {
        target.add(i);
    }
    //nodeIdx, curDist
    PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->(a[1]-b[1]));
    pq.offer(new int[]{s,0});
    boolean[] visited=new boolean[n];
    while(!pq.isEmpty()){
        int[] arr=pq.poll();
        int cur=arr[0];
        if(visited[cur]){
            continue;
        }
        if(target.contains(cur)){
            return arr[1];
        }
        visited[cur]=true;
        for (Integer next : maps[cur].keySet()) {
            pq.offer(new int[]{next,arr[1]+maps[cur].get(next)});
        }
    }
    return -1;
}