Shortest-Cycle-Containing-Target-Node

[azl397985856]

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 https://binarysearch.com/problems/Shortest-Cycle-Containing-Target-Node

[xinhaoyi]

Shortest Cycle Containing Target Node

Shortest Cycle Containing Target Node | binarysearch

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.

思路一

使用BFS即可，因为从target结点出发，使用BFS第一个回到target结点的肯定是最小的环，这个环的大小就是我们想要的解

我们额外维护一个visited[] 数组，用来保存某个结点是否被遍历过，如果遍历过了，那么这个结点就不要加入到队列中

代码

import java.util.*;

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);
                }
            }
            //The level of BFS
            level++;
        }

        return -1;
    }
}

[yachtcoder]

BFS O(n), O(n)

class Solution:
    def solve(self, graph, target):
        def bfs(target):
            queue = deque([[1, target]])
            visited = set([target])
            while queue:
                steps, u = queue.popleft()
                for v in graph[u]:
                    if v == target:
                        return steps
                    if v not in visited:
                        queue.append((steps+1, v))
                        visited.add(v)
            return -1
        return bfs(target)

[JiangyanLiNEU]

Idea

• BFS
• Starting from the target node, we increase result by 1 each time we visit its next node
• Also use a set so that we don't visit a node twice
• return the result when we visit target again, otherwise -1
• Runtime = O(V+E), Space = O(V)

  Python

  class Solution:
  def solve(self, graph, target):
      visited = set([])
      check = [target]
      result = 0
      while check:
          result += 1
          newCheck = []
          for vertex in check:
              for nextNode in graph[vertex]:
                  if nextNode == target:
                      return result
                  else:
                      if nextNode not in visited:
                          visited.add(nextNode)
                          newCheck.append(nextNode)
          check = newCheck
      return -1

  JavaScript

  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;
  }
  }

[nonevsnull]

思路

• 拿到题的直觉解法
  • 没做过这种邻接矩阵的类型，拿到题想了半天int[][] graph,这个构成是什么，原来可能是这种{{0}, {}, {2,3}}
  • graph的row长度是固定的，为顶点个数，每个row的长度是不固定的，取决于有没有edge
  • 题目的思路是直接从target出发来bfs，那么能第一个循环回来的，也就是最短的cycle length了
  • 注意需要标注visited，即要排除非target的循环

AC

代码

import java.util.*;

class Solution {
    public int solve(int[][] graph, int target) {
        int res = 0;
        if(graph[target].length == 0) return -1;
        Queue<Integer> q = new LinkedList<>();
        q.add(target);
        int[] visited = new int[graph.length];
        while(!q.isEmpty()){
            int size = q.size();
            res++;
            for(int i = 0;i < size;i++){
                int cur = q.poll();
                int[] neighbors = graph[cur];
                for(int neighbor: neighbors){
                    if(neighbor == target) return res;
                    if(visited[neighbor]++ > 0) continue;
                    visited[neighbor]++;
                    q.add(neighbor);
                }
            }
        }
        return -1;
    }
}

复杂度

time: O(V+E) space: O(V)

[Huangxuang]

题目：Shortest Cycle Containing Target Node

思路

• 找到最短的包含targe的环，那就可以以target为root，开始BFS，第一次找到target的层数+ 1 就是最终的环的长度

代码

import java.util.*;

class Solution {
    public int solve(int[][] graph, int target) {
        HashSet<Integer> visited = new HashSet();
        Queue<Integer> fringe = new ArrayDeque();
        visited.add(target);
        fringe.offer(target);

        int res = 0;
        while (!fringe.isEmpty()) {
            int size = fringe.size();
            for (int i = 0; i < size; i++) {
                int cur = fringe.poll();
                for (int neighbor : graph[cur]) {
                    if (neighbor == target) {
                        return res + 1;
                    }
                    if (visited.contains(neighbor)) {
                        continue;
                    }
                    visited.add(neighbor);
                    fringe.offer(neighbor);
                }
            }
            res++;
        }

        return -1;
    }
}

复杂度分析

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

[zhy3213]

思路

BFS+visited数组剪枝

代码

    def solve(self, graph, target):
        import queue
        if len(graph[target])==0:
            return -1
        if target in graph[target]:
            return 1
        visited = [False] * len(graph)
        q = graph[target]
        res=1
        while not len(q)==0:
            res+=1
            tmp= []
            for j in q:
                for i in graph[j]:
                    if not visited[i]:
                        if i==target:
                            return res
                        tmp.append(i)
                        visited[i]=True
            q=tmp
        return -1

[kidexp]

Thoughts

相当于找没有权重的最短路径一般就是BFS

code

from collections import deque, defaultdict

class Solution:
    def solve(self, graph, target):
        if not graph:
            return -1
        graph_dict = defaultdict(list)
        m = len(graph)
        for i in range(m):
            for j in graph[i]:
                graph_dict[i].append(j)
        queue = deque([target])
        visited_set = set()
        level = 0
        while queue:
            level += 1
            queue_size = len(queue)
            for _ in range(queue_size):
                node = queue.pop()
                for next_node in graph_dict[node]:
                    if next_node == target:
                        return level
                    elif next_node not in visited_set:
                        visited_set.add(next_node)
                        queue.appendleft(next_node)
        return -1

complexity

E 为Edge数目 E为node数目

Time O(E)

Space O(V)

[laofuWF]

# do bfs from target and the next time target is reached again, the distance is the res

class Solution:
    def solve(self, graph, target):
        queue = [target]
        distance = 0
        target_met = 0
        visited = [0 for i in range(len(graph))]

        while queue:
            curr_size = len(queue)
            distance += 1
            for i in range(curr_size):
                node = queue.pop(0)

                for neighbor in graph[node]:
                    if neighbor == target: return distance
                    if visited[neighbor] == 0:
                        queue.append(neighbor)
                        visited[node] = 1

        return -1

[skinnyh]

Note

• graph[i] means the adjacent nodes of node i. We can do BFS from the target node to see if we can find a cycle. If found it then return the shorted cycle length.

Solution

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

Time complexity: O(V + E)

Space complexity: O(V)

[ZacheryCao]

Idea:

BFS

Code:

class Solution:
    def solve(self, graph, target):
        seen = set()
        l = [target]
        length = 0
        while l:
            length += 1
            nl = []
            for i in l:
                for u in graph[i]:
                    if u == target:
                        return length
                    if u in seen:
                        continue
                    seen.add(u)
                    nl.append(u)
            l = nl
        return -1

Complexity:

Time: O(V + E) Space: O(V)

[joeytor]

思路

使用 BFS 的思路, 从 target 开始

每次添加 q 中元素的 neighbor 到 queue, 并且将 已经访问的节点添加到 visited

每一次 bfs 结束 step += 1

最后 如果 再次碰到 target, 返回 step

否则返回 -1

from collections import deque

class Solution:
    def solve(self, graph, target):
        n = len(graph)
        q = deque()
        step = 0
        q.append(target)
        visited = set()
        while q and step <= n:
            for i in range(len(q)):
                j = q.popleft()
                if j == target and step != 0:
                    return step
                if j in visited:
                    continue
                visited.add(j)
                for k in graph[j]:
                    q.append(k)

            step += 1
        return -1

复杂度

n 为 graph 的节点数目, e 为 边的数目

时间复杂度: O(n+e) graph 中每个节点最多加入 queue 一次, 遍历节点 neighbor 时每条边都可能被访问

空间复杂度: O(n) queue 的空间复杂度

[pophy]

思路

• BFS模板
  • 从target开始查找， 当再次碰到target的时候 说明图中有环，返回答案

Java Code

    public int solve(int[][] graph, int target) {
        boolean[] visited = new boolean[graph.length];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(target);
        visited[target] = true;
        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                for (int next : graph[cur]) {
                    if (next == target) {
                        return step + 1;
                    } else if (!visited[next]) {
                        visited[next] = true;
                        queue.add(next);
                    }
                }
            }
            step++;
        }
        return -1;
    }

时间&空间

• 时间 O(n)
• 空间 O(n)

[chenming-cao]

解题思路

BFS。BFS适合解决最短距离问题。以target为起点开始BFS，计算各个点到target的距离，同时建立visited集合来记录访问过的点。如果正在访问的点是target，则出现shortest cycle containing target node，返回结果即可，如果遍历结束target未再次出现，则返回-1。注意图中有环，如果将环中的点再次加入队列中会造成死循环。这时注意用visited集合进行判断，如果点在集合中出现，说明环出现，该点不在加入队列中。

代码

class Solution {
    public int solve(int[][] graph, int target) {
        Deque<Integer> queue = new LinkedList<>();
        queue.offer(target);
        int level = 0;
        Set<Integer> visited = new HashSet<>(); // use set to track visited nodes, used to check cycles
        // stop the while loop when all the edges have been checked
        while (!queue.isEmpty()) {   
            // visit nodes level by level         
            level++;
            Set<Integer> levelnodes = new HashSet<>(); // use to store nodes in the current level, exclude duplicates, this set is not necessary
            int size = queue.size(); // save initial queue's size here, cannot use queue.size() in the for loop, because queue.size() keeps changing
            for (int j = 0; j < size; j++) {
                int node = queue.poll();
                visited.add(node);                
                for (int neighbor: graph[node]) {
                    levelnodes.add(neighbor);
                }
            }
            for (int cur: levelnodes) {
                // detect a cycle
                if (visited.contains(cur)) {
                    if (cur == target) return level; // level is the length of the shortest cycle
                }
                else queue.offer(cur); // if no cycle, put node in this level into the queue
            }           
        }       
        return -1;        
    }
}

复杂度分析

• 时间复杂度：O(n + m)，n为顶点数，m为边数
• 空间复杂度：O(n)

[Daniel-Zheng]

思路

BFS。

代码(C++)

int solve(vector<vector<int>>& graph, int target) {
    queue<int> q;
    q.push(target);
    unordered_set<int> visited;
    int step = 0;
    while (!q.empty()) {
        int len = q.size();
        for (int i = 0; i < len; i++) {
            auto cur = q.front();
            q.pop();
            visited.insert(cur);
            for (auto& it : graph[cur]) {
                if (!visited.count(it)) {
                    q.push(it);
                } else if (it == target) {
                    return step + 1;
                }
            }
        }
        step += 1;
    }
    return -1;
}

复杂度分析

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

[wangyifan2018]

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

[JK1452470209]

思路

判断是否有环科院借用visited数组标记，同理找出有环也可以用visited寻找。要找出最短路径 需要记录层数。用bfs会很方便。

代码

    public int sovle(int[][] graph,int target){
            Queue<Integer> queue = new LinkedList<>();
            HashSet<Integer> visited = new HashSet<>();
            queue.offer(target);
            visited.add(target);
            int level = 0;
            while (!queue.isEmpty()){
                level++;
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    Integer node = queue.poll();
                    visited.add(node);
                    for (int c_node : graph[node]) {
                        if (visited.contains(c_node)){
                            if (c_node == target){
                                return level;
                            }
                        }else {
                            queue.offer(c_node);
                        }
                    }
                }
            }
            return -1;
        }

复杂度

时间复杂度：O(N)

空间复杂度: O(N)

[mmboxmm]

思路

BFS

代码

    public int solve(int[][] graph, int target) {
        boolean[] visited = new boolean[graph.length];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(target);
        visited[target] = true;
        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                for (int next : graph[cur]) {
                    if (next == target) {
                        return step + 1;
                    } else if (!visited[next]) {
                        visited[next] = true;
                        queue.add(next);
                    }
                }
            }
            step++;
        }
        return -1;
    }

[wenlong201807]

代码块

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;
  }
}

[ghost]

题目

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

思路

BFS + Adjacency list

代码

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

        while(queue):
            for i in range(len(queue)):
                node = queue.popleft()
                visited.add(node)

                for neighbor in graph[node]:
                    if neighbor == target:
                        return res+1
                    elif neighbor not in visited:
                        queue.append(neighbor)

            res+=1

        return -1

复杂度

Space: O(V) Time: O(V+E)

[user1689]

题目

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

思路

BFS+set

python3

class Solution:
    def solve(self, graph, target):
        # corner case:
        # graph = [
        #  [1],
        #  [1]
        # ]
        # target = 0
        queue = collections.deque([target])
        s = set()
        step = 0
        while (queue):
            size = len(queue)
            for _ in range(size):
                begin = queue.popleft()
                s.add(begin)
                for neighbor in graph[begin]:
                    if neighbor not in s:
                        queue.append(neighbor)
                    elif neighbor == target:
                        return step + 1
            step += 1
        return -1

复杂度分析

• time v + e v 节点数, e 为边数
• space v

相关题目

1. 待补充

[laurallalala]

代码

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

        while(queue):
            for i in range(len(queue)):
                node = queue.popleft()
                visited.add(node)

                for neighbor in graph[node]:
                    if neighbor == target:
                        return res+1
                    elif neighbor not in visited:
                        queue.append(neighbor)

            res+=1

        return -1

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

[AruSeito]

// 打卡占坑防踢

[ychen8777]

思路

以target为起点，试图 bfs 遍历回 target

代码

import java.util.*;

class Solution {
    public int solve(int[][] graph, int target) {

        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        int step = 0;

        queue.offer(target);

        while(!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int curNode = queue.poll();
                visited.add(curNode);
                int[] neighbors = graph[curNode];

                for (int num : neighbors) {
                    if(!visited.contains(num)) {
                        queue.offer(num);
                    }

                    if (num == target) {
                        return step + 1;
                    }

                }
            }

            step++;

        }

        return -1;

    }
}

复杂度

时间：O(V + E) \ 空间：O(V)

[ai2095]

Shortest Cycle Containing Target Node

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

Topics

• BFS

思路

Start from target and do BFS till reach target for the first time.

代码 Python

class Solution:
    def solve(self, graph, target):
        visited = set(target)
        q = deque([target])
        length = -1
        while q:
            length += 1
            size = len(q)
            for _ in range(size):
                cur_node = q.popleft()
                for next_node in graph[cur_node]:
                    if next_node == target:
                        return length
                    elif next_node not in visited:
                        q.append(next_node)
                        visited.append(next_node)
        return  -1

复杂度分析

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

[ForLittleBeauty]

思路

---

从Target开始，使用BFS，将遇到过的点加入visited set，一旦遇到重复的点，则直接返回走过的steps。如果没有遇到重复的点，则返回-1，说明target不在环中。

代码

---

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

---

时间复杂度

O(V+E)

空间复杂度

O(V)

[wangzehan123]

import java.util.*;

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

        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;
    }
}

[Mrhero-web]

import java.util.*;

class Solution { public int solve(int[][] graph, int target) {

    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();
    int step = 0;

    queue.offer(target);

    while(!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int curNode = queue.poll();
            visited.add(curNode);
            int[] neighbors = graph[curNode];

            for (int num : neighbors) {
                if(!visited.contains(num)) {
                    queue.offer(num);
                }

                if (num == target) {
                    return step + 1;
                }

            }
        }

        step++;

    }

    return -1;

}

}

[james20141606]

Day 52: 694. Shortest Cycle Containing Target Node (search, BFS)

• Problem Link

  • 694. Shortest Cycle Containing Target Node

• Ideas

  • Use BFS, start searching from the target, use a set to record the visited value. If neighbor in the graph is equal to target, then we detect a cycle, else we append the neighbor to the queue for BFS

• Complexity: hash table and bucket

  • Time: O(V+E) #vertex + edges
  • Space: O(V)

• Code

class Solution:
    def solve(self, graph, target):
        queue = deque([target])  #search starts from target
        ans = 0
        visited = set()  #used to detect the cycle
        while queue:
            for _ in range(len(queue)):
                cur_val = queue.popleft()
                visited.add(cur_val)
                for neighbor in graph[cur_val]: #visit cur_val's neighbors
                    if neighbor == target:  #detect cycle, return
                        return ans + 1
                    elif neighbor not in visited:
                        queue.append(neighbor)  #add to queue, visit later
            ans += 1
        return -1     

• other resources:

[akxuan]

使用 bfs 时间复杂度：O(V+E) 空间复杂度：O(V)

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

        while(queue):
            for i in range(len(queue)):
                node = queue.popleft()
                visited.add(node)

                for neighbor in graph[node]:
                    if neighbor == target:
                        return res+1
                    elif neighbor not in visited:
                        queue.append(neighbor)

            res+=1

        return -1

[shixinlovey1314]

Title:Shortest Cycle Containing Target Node

Question Reference LeetCode

Solution

BFS: start from target and do a regular BFS

Code

int solve(vector<vector<int>>& graph, int target) {
    unordered_set<int> visited;
    // <node, step>
    queue <pair<int, int>> worker;
    worker.push(make_pair(target, 0));
    visited.insert(target);

    while (!worker.empty()) {
        int node = worker.front().first;
        int step = worker.front().second;
        worker.pop();

        for (int j = 0; j < graph[node].size(); j++) {
            if (graph[node][j] == target) {
                return step + 1;
            }

            if (!visited.count(graph[node][j])) {
                worker.push(make_pair(graph[node][j], step + 1));
                visited.insert(graph[node][j]);
            }
        }
    }

    return -1;
}

Complexity

Time Complexity and Explanation

O(m*n) need visit each node once

Space Complexity and Explanation

O(n) to maintain the visited array.

[hwpanda]

class Solution:
   def solve(self, graph, target):
      visited = set()
      l = [target]
      length = 0

      while l:
         length += 1
         nl = []
         for u in l:
            for v in graph[u]:
               if v == target:
                  return length
               if v in visited:
                  continue
               visited.add(v)
               nl.append(v)
         l = nl

      return -1

[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;
    }
}

[Yufanzh]

Intuition

Using BFS. To check if a graph has circle, we need a visited set to check if neighbor node is in the visited set or not.\ If we started searching from target, it will be more convenient than start from starting node, check if graph has circle, then check if circle contains target.

Algorithm in python3

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

Complexity Analysis

• Time complexity: O(v+e) where v is the node and e is the edge
• Space complexity: O(v)

[muimi]

思路

从target开始的反向BFS

代码

class Solution {
    public int solve(int[][] graph, int target) {
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[graph.length];
        q.offer(target);
        int level = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int cur = q.poll();
                visited[cur] = true;
                for (int neighbor : graph[cur]) {
                    if (neighbor == target) return level + 1;
                    if (!visited[neighbor]) q.offer(neighbor);
                }
            }
            level++;
        }
        return -1;
    }
}

复杂度

• 时间复杂度：O(节点数+边数)
• 空间复杂度：O(节点数)

[ginnydyy]

Problem

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

Notes

• BFS (target as source)
• To check if there is a cycle containing the target as a node, instead of using BFS starting from the first node (0) to find a cycle then check whether the cycle contains the target, we can use BFS starting from the target and check whether there is a cycle.
• Details:
  • need to record the visited nodes to avoid infinite loop.
  • need to check whether the neighbor is target before checking whether the neighbor has been visited.
  • in order to count the number of nodes, need to do the BFS layer by layer, which means need to increment the count once, then mark the current queue size, and process the nodes within the current queue size (the nodes in the current layer). Then the next while loop will increment the count again and then process the next layer of nodes.

Solution

import java.util.*;

class Solution {
    public int solve(int[][] graph, int target) {
        if(graph == null || graph.length == 0 || target < 0 || target >= graph.length){
            return -1;
        }

        boolean[] visited = new boolean[graph.length]; 
        int count = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(target);
        visited[target] = true;
        while(!queue.isEmpty()){
            count++;
            int size = queue.size();
            for(int i = 0; i < size; i++){
                int curr = queue.poll();
                for(int neighbor: graph[curr]){
                    if(neighbor == target){
                        return count;
                    }
                    if(visited[neighbor]){
                        continue;
                    }
                    queue.offer(neighbor);
                    visited[neighbor] = true;
                }
            }

        }

        return -1;
    }
}

Complexity

• Time: O(v + e) v is the number of nodes, e is the number of edges of the nodes.
• Space: O(v).

[thinkfurther]

思路

层序遍历

代码

class Solution:
    def solve(self, graph, target):
        import collections
        q = collections.deque()
        q.append(target)
        step = 0
        visit = set()
        while q:
            for _ in range(len(q)):
                cur = q.popleft()
                visit.add(cur)

                for n in graph[cur] :
                    if n == target:
                        return step + 1
                    if n not in visit:
                        q.append(n)
            step += 1

        return -1

复杂度

时间复杂度 ：O(v+e)

空间复杂度：O(v)

[itsjacob]

Intuition

• BFS starting from the target node
• Notice the target value is also the vertex index in the adjacency list

Implementation

int solve(vector<vector<int>> &graph, int target)
{
  // BFS approach starting from the target vertex
  // target is also the index in the adjacency list
  std::unordered_set<int> visited(graph.size());
  std::queue<int> aQueue;
  int res{ -1 };
  aQueue.push(target);
  int depth{ 0 };
  while (!aQueue.empty()) {
    int qSize = aQueue.size();
    depth++;
    for (int ii = 0; ii < qSize; ii++) {
      int curVertex = aQueue.front();
      aQueue.pop();
      for (auto const &neighbor : graph[curVertex]) {
        if (neighbor == target) {
          return depth;
        }
        if (visited.count(neighbor)) continue;
        visited.insert(neighbor);
        aQueue.push(neighbor);
      }
    }
  }
  return -1;
}

Complexity

• Time complexity: O(mn)
• Space complexity: O(n)

[ymwang-2020]

class Solution:
    def solve(self, graph, target):
        import collections
        q = collections.deque()
        q.append(target)
        step = 0
        visit = set()
        while q:
            for _ in range(len(q)):
                cur = q.popleft()
                visit.add(cur)

                for n in graph[cur] :
                    if n == target:
                        return step + 1
                    if n not in visit:
                        q.append(n)
            step += 1

        return -1

[sxr000511]

class Solution: def solve(self, graph, target): visited = set() l = [target] length = 0

  while l:
     length += 1
     nl = []
     for u in l:
        for v in graph[u]:
           if v == target:
              return length
           if v in visited:
              continue
           visited.add(v)
           nl.append(v)
     l = nl

  return -1

[zhangzz2015]

思路

• 题目找最小的环，可以转化为从target 到 target 最短路径问题，最短路径选择BFS方法，标准的BFS方法，唯一要注意最后退出条件，因为起点和终点都是target。可以利用visit flag，排除掉起点退出。时间复杂度为O(N)，空间复杂度为 O(N)。

int solve(vector<vector<int>>& graph, int target) {

    queue<int> que; 

    que.push(target);
    vector<bool> visit(graph.size(), false);  

    int level =0; 
    while(que.size())
    {
        int iSize = que.size(); 
        for(int i=0; i< iSize; i++)
        {
            int topNode = que.front(); 
            que.pop(); 

            if(topNode == target && visit[topNode])
               return level; 
            if(visit[topNode])
               continue;

           visit[topNode] = true; 
           for(int j =0; j< graph[topNode].size(); j++)
           {
                   que.push(graph[topNode][j]); 
           }
        }

        level++; 
    }

    return -1; 

}

[ysy0707]

思路：BFS

import java.util.*;

class Solution {
    public int solve(int[][] graph, int target) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        queue.offer(target);
        int res = 0;
        while(!queue.isEmpty()){
            res++;
            int size = queue.size();
            for(int i = 0; i < size; i++){
                int cur = queue.poll();
                for(int nxt : graph[cur]){
                    if(nxt == target){
                        return res;
                    }
                    if(visited.contains(nxt)){
                        continue;
                    }
                    visited.add(nxt);
                    queue.offer(nxt);
                }
            }
        }
        return -1;
    }
}

时间复杂度：O(N^2) 空间复杂度：O(N)

[biancaone]

class Solution:
    def solve(self, graph, target):
        if not graph:
            return -1

        q = collections.deque([target])
        visited = set([target])
        result = 0

        while q:
            for _ in range(len(q)):
                cur = q.popleft()
                for neighbor in graph[cur]:
                    if neighbor == target:
                        return result + 1
                    else:
                        if neighbor not in visited:
                            visited.add(neighbor)
                            q.append(neighbor)

            result += 1

        return -1

[RocJeMaintiendrai]

题目

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.

思路

BFS

代码

class Solution {
    public int solve(int[][] graph, int target) {
        int res = 0;
        final int len = graph.length;
        boolean visited = new boolean[len];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(target);
        while(!queue.isEmpty()) {
            final int num = queue.size();
            for(int i = 0; i < num; i++) {
                int cur = queue.remove();
                visited[cur] = true;
                for(int neighbor : graph[cur]) {
                    if(neighbor == target) {
                        return res + 1;
                    } else if(!visited[neighbor]) {
                        queue.add(neighbor);
                    }
                }
            }
            res++;
        }
        return -1;
    }
}

复杂度分析

时间复杂度

O(E + V)

空间复杂度

O(E)

[Francis-xsc]

思路

bfs

代码

int solve(vector<vector<int>>& graph, int target) {
    for(auto x:graph[target]){
        if(x==target)
            return 1;
    }
    struct st{
        int cnt;
        int val;
        st(int c,int v):cnt(c),val(v){};
    };
    queue<st>q;
    q.push(st(1,target)); 
    vector<bool>visited(graph.size(),false);
    while(!q.empty()){
        int curCnt=q.front().cnt;
        int curVal=q.front().val;
        if(curVal==target){
            if(curCnt!=1){
                return curCnt-1;
            }
        }
        else{
            visited[curVal]=1;
        }
        for(auto x:graph[curVal]){
            if(x==curVal||visited[x])
                continue;
            q.push(st(curCnt+1,x));
        }
        q.pop();
    }
    return -1;
}

[leolisgit]

题目

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

思路

题目是找一个可能存在的最小环的长度。使用BFS进行遍历。

代码

class Solution {
    public int solve(int[][] graph, int target) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();

        int res = 0;
        queue.offer(target);
        while (!queue.isEmpty()) {
            int n = queue.size();
            res++;
            for (int i = 0; i < n; i++) {
                int cur = queue.poll();
                for (int nei : graph[cur]) {
                    if (nei == target) {
                        return res;
                    }
                    if (visited.contains(nei)) {
                        continue;
                    }
                    queue.offer(nei);
                    visited.add(nei);
                }
            }
        }
        return -1;
    }
}

复杂度

时间：O(v + e) 空间：O(v)

[zhiyuanpeng]

class Solution:
    def solve(self, graph, target):
        visited = set([])
        check = [target]
        result = 0
        while check:
            result += 1
            newCheck = []
            for vertex in check:
                for nextNode in graph[vertex]:
                    if nextNode == target:
                        return result
                    else:
                        if nextNode not in visited:
                            visited.add(nextNode)
                            newCheck.append(nextNode)
            check = newCheck
        return -1

[Bingbinxu]

方法 理解输入的核心：数组下标访问的元素对应下一个数组下标 代码

实现语言: C++
int solve(vector<vector<int>>& graph, int target) {
    queue<int> q;
    q.push(target);
    unordered_set<int> visited;
    int step = 0;
    while (!q.empty()) {
        int len = q.size();
        for (int i = 0; i < len; i++) {
            auto cur = q.front();
            q.pop();
            visited.insert(cur);
            for (auto& it : graph[cur]) {
                //return it;
                if (!visited.count(it)) {
                    q.push(it);
                } else if (it == target) {
                    return step + 1; //满足情况状态弹出加一
                }
            }
        }
        step += 1;//结束了一格q列表，加一
    }
    return -1;   
}

复杂度分析 时间复杂度: O(v+e)，v节点数，e边数 空间复杂度: O(v)

[BreezePython]

思路

BFS

代码

class Solution:
    def solve(self, graph, target):
        if not graph:
            return -1

        q = collections.deque([target])
        visited = set([target])
        result = 0

        while q:
            for _ in range(len(q)):
                cur = q.popleft()
                for neighbor in graph[cur]:
                    if neighbor == target:
                        return result + 1
                    else:
                        if neighbor not in visited:
                            visited.add(neighbor)
                            q.append(neighbor)

            result += 1

        return -1

复杂度

• 时间复杂度：O(N)
• 空间复杂度：O(N)

[chen445]

思路

BFS

代码

class Solution:
    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

复杂度

Time: O(E+V) V is the number of nodes, e is the number of edges

Space: O(V)

[florenzliu]

Explanation

• bfs

Python

class Solution:
    def solve(self, graph, target):
        queue = [target]
        dist = 0
        visited = [0 for _ in range(len(graph))]
        while queue:
            for _ in range(len(queue)):
                curr = queue.pop(0)
                visited[curr] = 1
                for neighbour in graph[curr]:
                    if neighbour == target:
                        return dist + 1
                    if not visited[neighbour]:
                        queue.append(neighbour)  
            dist += 1
        return -1

Complexity

• Time: O(V+E) where V is the number of vertices
• Space: O(V)