【Day 52 】2022-02-01 - Shortest-Cycle-Containing-Target-Node

[azl397985856]

Shortest-Cycle-Containing-Target-Node

入选理由

暂无

题目地址

https://binarysearch.com/problems/Shortest-Cycle-Containing-Target-Node

前置知识

• BFS

  题目描述

  You are given a two-dimensional list of integers graph representing a directed graph as an adjacency list. You are also given an integer target.

Return the length of a shortest cycle that contains target. If a solution does not exist, return -1.

Constraints

n, m ≤ 250 where n and m are the number of rows and columns in graph

[luhnn120]

思路

bfs

代码

const shortestCircle = (graph, target) => {
  let seen  = false;
  for (let i = 0; i < graph.length; i ++ ) {
    if (graph[i][0] === target ) {
      seen = true; 
      targetPos = i
    }
    if (!graph[i][0]) return -1
  }
  return graph.length 
};

复杂度

空间复杂度 O(1) 时间复杂度 O(N)

[shamworld]

class Solution {
    solve(graph, target) {
        let result = 0;
        let visited = new Set([]);
        let check = [target];
        let length = check.length;
        while (length > 0) {
        result++;
        for (let i = 0; i < length; i++) {
            let vertex = check.shift();
            for (let nextNode of graph[vertex]) {
                if (nextNode === target) {
                    return result;
                } else {
                    if (!visited.has(nextNode)) {
                    visited.add(nextNode);
                    check.push(nextNode);
                    }
                }
            }
        }
        length = check.length;
        }
        return -1;
    }
}

[GaoMinghao]

思路

可以想到需要从target开始往外遍历，以及BFS，但是写代码的时候发现对环的处理还有问题

代码

import java.util.*;

class Solution {
    public int solve(int[][] graph, int target) {
        boolean[] visited = new boolean[graph.length];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(target);
        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for(int i = 0; i < size; i++) {
                int point = queue.remove();
                visited[point] = true;
                for(int j = 0; j < graph[point].length; j++) {
                    int neighbour = graph[point][j];
                    if(!visited[neighbour])
                        queue.add(neighbour);
                    else if(neighbour == target)
                        return steps+1;
                }
            }
            steps++;    
        }
        return -1;
    }
}

[zzzpppy]

import java.util.*;

class Solution {
    public int solve(int[][] graph, int target) {
        boolean[] visited = new boolean[graph.length];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(target);
        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for(int i = 0; i < size; i++) {
                int point = queue.remove();
                visited[point] = true;
                for(int j = 0; j < graph[point].length; j++) {
                    int neighbour = graph[point][j];
                    if(!visited[neighbour])
                        queue.add(neighbour);
                    else if(neighbour == target)
                        return steps+1;
                }
            }
            steps++;    
        }
        return -1;
    }
}

[pf135145]

class Solution:
    def solve(self, graph, target):
        queue = collections.deque([target])
        visited = set()
        res = 0
        while queue:
            res += 1
            for _ in range(len(queue)):
                cur = queue.popleft()
                for nxt in graph[cur]:
                    if nxt == target:
                        return res
                    if nxt in visited:
                        continue
                    visited.add(nxt)
                    queue.append(nxt)
        return -1

[fornobugworld]

class Solution: def solve(self, graph, target): q = collections.deque([target]) visited = set() steps = 0 while q: for i in range(len(q)): cur = q.popleft() visited.add(cur) for neighbor in graph[cur]: if neighbor not in visited: q.append(neighbor) elif neighbor == target: return steps + 1 steps += 1 return -1

[WANGDI-1291]

代码

class Solution:
    def solve(self, graph, target):
        q = collections.deque([target])
        visited = set()
        steps = 0
        while q:
            for i in range(len(q)):
                cur = q.popleft()
                visited.add(cur)
                for neighbor in graph[cur]:
                    if neighbor not in visited:
                        q.append(neighbor)
                    elif neighbor == target:
                        return steps + 1
            steps += 1
        return -1

[Flower-F]

解题思路

反向遍历

代码

class Solution {
    solve(graph, target) {
        const queue = [target];
        const visited = new Set();
        let step = 0;

        while (queue.length) {
            const len = queue.length;
            for (let i = 0; i < len; i++) {
                const cur = queue.shift();

                for (const neighbor of graph[cur]) {
                    if (neighbor === target) {
                        return step + 1;
                    }
                    if (!visited.has(neighbor)) {
                        queue.push(neighbor);
                        visited.add(neighbor);
                    } 
                }
            }
            step++;
        }

        return -1;
    }
}

复杂度

时间：O(N) 空间：O(N)

[Richard-LYF]

class Solution: def solve(self, graph, target): q = collections.deque([target]) visited = set() steps = 0 while q: for i in range(len(q)): cur = q.popleft() visited.add(cur) for neighbor in graph[cur]: if neighbor not in visited: q.append(neighbor) elif neighbor == target: return steps + 1 steps += 1 return -1

[taojin1992]

// time: O(v+e)
// space: O(v)
// BFS, reverse from target 
import java.util.*;

class Solution {
    public int solve(int[][] graph, int target) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(target);

        Set<Integer> visited = new HashSet<>();
        int steps = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int cur = q.poll();
                visited.add(cur);
                for (int neighbor : graph[cur]) {
                    if (!visited.contains(neighbor)) {
                        q.offer(neighbor);
                    } else if (neighbor == target) {
                        return steps + 1;
                    }
                }

            }
            steps++;
        }
        return -1;
    }
}

[yijing-wu]

class Solution {
    public int solve(int[][] graph, int target) {
        //graph.length is the total number of the graph
        boolean[] visited = new boolean[graph.length];
        //generate the queue 
        Queue<Integer> q = new LinkedList<>();
        q.add(target);

        //the initial value is 0, as we don't add tartget knot, We think the target is level 0
        int level = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int tmp = q.remove();
                visited[tmp] = true;

                for (int neighbor : graph[tmp]) {
                    if (neighbor == target)
                        return level + 1;
                    else if (!visited[neighbor])
                        q.add(neighbor);
                }
            }
            level++;
        }

        return -1;
    }
}

[chen445]

def solve(self, graph, target):
        q=deque([target])
        level=0
        visited=set()
        while q:
            level+=1
            n=len(q)
            for i in range(n):
                node=q.popleft()
                for neigh in graph[node]:
                    if neigh == target:
                        return level
                    elif neigh not in visited:
                        visited.add(neigh)
                        q.append(neigh)
        return -1

[zol013]

class Solution:
    def solve(self, graph, target):
        queue = deque([target])
        steps = 0
        visited = set()

        while queue:
            for _ in range(len(queue)):
                node = queue.popleft()
                for neighbor in graph[node]:
                    if neighbor == target:
                        return steps + 1
                    if neighbor not in visited:
                        queue.append(neighbor)
                        visited.add(neighbor)
            steps += 1

        return -1

[jiaqiliu37]

class Solution:
    def solve(self, graph, target):
        queue = deque([target])
        seen = set()
        steps = 0

        while queue:
            for _ in range(len(queue)):
                node = queue.popleft()
                for neighbor in graph[node]:
                    if neighbor == target:
                        return steps + 1
                    if neighbor not in seen:
                        seen.add(neighbor)
                        queue.append(neighbor)
            steps += 1

        return -1

[1149004121]

Shortest Cycle Containing Target Node

思路

无权图的单源最短路算法，从target出发，将其neighbors入队，用BFS。

代码

var maxDistance = function(grid) {
    let n = grid.length;
    let queue = [];
    for(let i = 0; i < n; i++){
        for(let j = 0; j < n; j++){
            if(grid[i][j] === 1) queue.push([i, j]);
        }
    };
    if(queue.length === 0 || queue.length === n * n) return -1;
    let step = -1;
    let dir = [[-1, 0], [1, 0], [0, 1], [0, -1]];
    while(queue.length){
        let len = queue.length;
        for(let _ = 0; _ < len; _++){
            let position = queue.shift();
            for(let i = 0; i < 4; i++){
                let x = position[0] + dir[i][0];
                let y = position[1] + dir[i][1];
                if(x >= 0 && x < n && y >= 0 && y < n && grid[x][y] === 0){
                    grid[x][y] = -1;
                    queue.push([x, y]);
                }
            }
        };
        step++;
    };
    return step;
};

复杂度分析

• 时间复杂度：O(V + E)。
• 空间复杂度：O(V)。