azl397985856 commented 3 years ago

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

yanglr commented 3 years ago

思路:

本题的输入比较特别, 需要自己先好好理解一下。

理解题意:

示例 1

输入

graph = [
    [1],
    [2],
    [0]
]
target = 0

输入的解释:

index=0的结点的邻接nodes数组是: [1],

index=1的结点的邻接nodes数组是: [2],

index=2的结点的邻接nodes数组是: [0]

输出

解释

结点 0 -> 1 -> 2 -> 0 形成了一个环

示例 2

输入

graph = [
    [1],
    [2],
    [4],
    [],
    [0]
]
target = 3

输入的解释:

index=0的结点的邻接nodes数组是: [1],

index=1的结点的邻接nodes数组是: [2],

index=2的结点的邻接nodes数组是: [4],

index=3的结点的邻接nodes数组是: [], 为空, 表示没与之连接的相邻结点。

index=4的结点的邻接nodes数组是: [0]

输出

-1

提示 `#1`

试试从“目标”结点运行BFS广度优先搜索并记录“visited” set。

这个题首先要理解题目的输入 - 二维矩阵(adj list), 是一个邻接表。

其中

graph = [
    [1],
    [2],
    [0]
]

表示:

index=0的结点的邻接nodes数组是: [1],

index=1的结点的邻接nodes数组是: [2],

index=2的结点的邻接nodes数组是: [0]

方法: BFS

从目标节点target开始往后一层一层遍历

1.先遍历target向后连接的节点们，再遍历这些节点们向后连接的节点们

2.如果遍历回target了，那就返回到目前为止遍历的次数，也就是环的大小

3.如果循环结束也没有返回，说明target不在环里，返回-1

4.遍历的过程中，注意已经遍历过的节点不能再遍历了，否则循环结束不了

代码

实现语言: C++

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

复杂度分析

时间复杂度: O(n)，最差的情况是n个节点全遍历一遍
空间复杂度: O(n)，最差的情况是target与剩余所有的节点都连接上了

yingliucreates commented 3 years ago

link:

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

题目也没看懂，所以答案应该是错的

代码 Javascript

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

carsonlin9996 commented 3 years ago

思路

给的graph[][] 其实就是构好图的结果，在target 往外BFS就好了

代码


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

        Queue<Integer> queue = new ArrayDeque<>();
        Set<Integer> visited = new HashSet<>();

        queue.add(target);
        visited.add(target);
        int step = 0;

        while (!queue.isEmpty()) {

            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int curNode = queue.poll();

                for (int neighbor : graph[curNode]) {
                    if (neighbor == target) {
                        return step + 1;
                    }
                    if (!visited.contains(neighbor)) {
                        visited.add(neighbor);
                        queue.offer(neighbor);
                    }

                }
            }
            step++;
        }
        return -1;

    }
}

joeytor commented 3 years ago

思路

使用 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 的空间复杂度

yan0327 commented 3 years ago

思路：题目已知条件是一个邻接图和目标值，本题求的是最短周期。短 = 距离 = BFS优先。因此可以用BFS求解，将目标节点放入队列，扫描邻接数组，每次扫描加一。如果遇到目标节点则直接返回，如果遇到已经遍历过的节点继续continue循环，遇到一个新的节点要标志位置1【用一个哈希表存是否到过该节点】。最后，如果for循环结束还没找到回去的节点，则返回-1。代表目标节点不处于循环内

func solve(graph [][]int, target int) int{
    q := []int{}
    hashmap := map[int]int{}
    q = append(q,target)
    out := 0
    for len(q) >0{
        out++
        cur := q[0]
        q = q[1:]
        for _,next := range graph[cur]{
            if next == target{
                return out
            }
            if _,ok := hashmap[next];ok{
                continue
            }
            hashmap[next]++
            q = append(q,next)
        }
    }
    return -1
}

时间复杂度：O（n）空间复杂度：O（n）

falconruo commented 3 years ago

思路: graph的第一维索引代表一个节点，第二维代表该节点向后连接的节点(邻接节点)

广度优先遍历，
- 以target节点为起始节点，依次遍历当前队首节点的邻居节点，使用辅助队列qt存放未访问过的邻居节点，visited来记录访问过的节点，每次loop长度加一
- 终止条件是遇到起始节点target
- 队列空则表示没有环，返回-1

复杂度分析:

时间复杂度: O(N), 其中N是graph的长度
空间复杂度: O(N), 辅助队列空间，极限情况所有的节点入队

代码(C++):

int solve(vector<vector<int>>& graph, int target) {
    queue<int> qt;
    set<int> visited;
    int res = 0;

    qt.push(target);

    while (!qt.empty()) {
        size_t size = qt.size();

        while (size--) {
            int cur = qt.front();
            qt.pop();
            visited.insert(cur);

            for (auto n : graph[cur]) { // all adjacent nodes of node[cur]
                if (!visited.count(n))
                    qt.push(n);
                else if (n == target)
                    return res + 1;

            }
        }
        ++res;
    }

    return -1;
}

tongxw commented 3 years ago

思路

BFS带层搜索模板，从target开始到target结束。

代码

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

        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[graph.length];
        q.offer(target);

        int step = -1;
        while (!q.isEmpty()) {
            step++;
            int size = q.size();
            for (int i=0; i<size; i++) {
                int v = q.poll();
                if (v == target && step != 0) {
                    return step;
                }

                for (int adj : graph[v]) {
                    if (!visited[adj]) {
                        visited[adj] = true;
                        q.offer(adj);
                    }
                }
            }
        }

        return -1;
    }
}

TC: O(v + e) SC: O(v)

ZiyangZ commented 3 years ago

Brute force: DFS

class Solution {
int ans = 0;
public int solve(int[][] graph, int target) {
    ans = 2 * graph.length;
    int[] visited = new int[graph.length];
    for (int next: graph[target]) {
        dfs(next, graph, target, visited, 1);
    }
    if (ans == 2 * graph.length) return -1;
    return ans;
}

public void dfs(int cur, int[][] graph, int target, int[] visited, int distance) {
    if (cur == target) {
        ans = Math.min(ans, distance);
        return;
    }

    if (visited[cur] == 1) return;
    visited[cur] = 1;
    for (int next: graph[cur]) {
        dfs(next, graph, target, visited, distance + 1);
    }
    visited[cur] = 0;
}
}

BFS is ideal for calculating distance in graph problems.

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

st2yang commented 3 years ago

思路

bfs

代码

python

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

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

        steps += 1

    return -1

复杂度

时间: O(n)
空间: O(n)

V-Enzo commented 3 years ago

思路

图的题，一般可以使用bfs或者dfs进行求解。
在此题中，以target节点为起始节点，然后找它指向的节点，最后看能否返回自身。如果不能返回自身则return -1;

需要使用队列进行bfs遍历。

int solve(vector<vector<int>>& graph, int target) {
int N = graph.size();
int M = graph[0].size();
int path_len = 0;
queue<int> q;
unordered_set<int> visited;
q.push(target);
while(!q.empty())
{
    path_len++;
    int N = q.size();
    for(int i=0; i<N; i++)
    {
        int front = q.front();
        q.pop();
        for(int neighbor:graph[front])
        {
            if(neighbor == target)
            {
                return path_len;
            }
            if(visited.count(neighbor))
            {
                continue;
            }
            visited.insert(neighbor);
            q.push(neighbor);
        }
    }

}
return -1;
}

Complexity:

Time:O(n) Space:O(n)

Menglin-l commented 3 years ago

bfs。从target开始遍历，第一次再遇到target时最小的环出现。

代码部分：

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

        int len = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i ++) {
                int t = queue.remove();
                visited[t] = true;

                for (int neighbor : graph[t]) {
                    if (neighbor == target) return len + 1;
                    else if (!visited[neighbor]) queue.add(neighbor);
                }
            }
            len ++;
        }
        return -1;
    }
}

复杂度：

Time: O(V + E)

Space: O(V)，V为graph的顶点数

mixtureve commented 3 years ago

思路

shortest path 想 bfs。另外一个重点在于想清楚要 offer 进 queue 的 initial value 是什么

Java Code:


import java.util.*;

class Solution {
    public int solve(int[][] graph, int target) {
        // reurn a cycle, what if there is no cycle. how to show there is a cycle, visited
        // when find the target make a flag as true
        // need to do for loops, b/c of islated points
        // how many nodes?  n nodes
        // shortest path: bfs
        Set<Integer> visited = new HashSet<>();
        Deque<Integer> queue = new ArrayDeque<>();
        // initial nodes? target node? is target for sure to be the the graph?
        queue.offer(target);
        visited.add(target);
        int path = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                if (path != 0 && cur == target) {
                    return path;
                }

                for (int nei: graph[cur]) {
                    if (nei == target || !visited.contains(nei)) {
                        queue.offer(nei);
                        visited.add(nei);
                    }
                }
            }
            path++;
        }
        return -1;
    }
}

复杂度分析

n 是 rows 的长度，同时也是 nodes 的个数

时间复杂度：$O(n)$
空间复杂度：$O(n)$

Bingbinxu commented 3 years ago

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

实现语言: 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)

zszs97 commented 3 years ago

开始刷题

题目简介

【Day 52 】2021-10-31 - Shortest-Cycle-Containing-Target-Node

题目思路

BFS

题目代码

代码块

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)

winterdogdog commented 3 years ago

没太看懂题目，先抄一个

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

yiwchen commented 3 years ago

BFS:

from collections import deque
class Solution:
    def solve(self, graph, target):
        q = deque([target])
        visited = set()
        length = 0
        while q:
            level = deque([])
            while q:
                cur = q.popleft()
                visited.add(cur)
                for item in graph[cur]:
                    if item not in visited:
                        level.append(item)
                    else:
                        if item == target:
                            return length + 1
            q = level
            length += 1
        return -1

wenlong201807 commented 3 years ago

代码块


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(n)
空间复杂度 O(1)

q815101630 commented 3 years ago

补作业

这道题的重点在于如何看懂这个图，hhh，使用标准bfs可以做

class Solution:
    def solve(self, graph, target):
        queue = deque([target])
        cnt = 0
        seen = set()
        first = True
        found = False
        while queue:
            curLen = len(queue)
            for _ in range(curLen):
                popped = queue.popleft()
                if (not first) and popped == target:
                    return cnt 
                for i in graph[popped]:
                    if i not in seen:
                        seen.add(i)
                        queue.append(i)
            first = False
            cnt+=1
        return -1

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

leetcode-pp / 91alg-5-daily-check

【Day 52 】2021-10-31 - Shortest-Cycle-Containing-Target-Node #70

Shortest-Cycle-Containing-Target-Node

入选理由

题目地址

前置知识

题目描述

思路:

示例 1

输入

输出

解释

示例 2

输入

输出

提示 #1

方法: BFS

代码

复杂度分析

link:

代码 Javascript

思路

代码

思路

复杂度

思路

代码

思路

代码

复杂度

思路

Complexity:

bfs。从target开始遍历，第一次再遇到target时最小的环出现。

代码部分：

复杂度：

Time: O(V + E)

Space: O(V)，V为graph的顶点数

思路

开始刷题

题目简介

【Day 52 】2021-10-31 - Shortest-Cycle-Containing-Target-Node

题目思路

题目代码

代码块

复杂度

代码块

时间复杂度和空间复杂度

补作业

提示 `#1`