azl397985856 commented 2 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

ZacheryCao commented 2 years ago

Idea:

BFS

Code:

class Solution:
    def solve(self, graph, target):
        seen = set()
        if target <0 or target>=len(graph):
            return -1
        stack = collections.deque()
        stack.append(target)
        ans = 1
        while stack:
            l = len(stack)
            for _ in range(l):
                cur = stack.popleft()
                if cur not in seen:
                    seen.add(cur)
                    for nei in graph[cur]:
                        if nei == target:
                            return ans
                        else:
                            if nei not in seen:
                                stack.append(nei)
            ans += 1
        return -1

Complexity:

Time: O(N)

Space: O(N)

JiangWenqi commented 2 years ago

C++

BFS

int solve(vector<vector<int>> &graph, int target) {
    queue<int> q;
    vector<bool> visited(graph.size(), false);
    for (int &v : graph[target]) q.push(v);
    int res = 0;
    while (!q.empty()) {
        int sz = q.size();
        res++;
        for (int i = 0; i < sz; i++) {
            int v = q.front();
            q.pop();
            visited[v] = true;
            if (v == target) return res;
            for (int &u : graph[v]) {
                if (!visited[u]) q.push(u);
            }
        }
    }

    return -1;
}

MichaelXi3 commented 2 years ago

Idea

本题是一个经典的 BFS，可使用 BFS 模版。

一个 Queue 去记录 neighbors nodes 以帮助横向展开搜索 🔍
一个 hasVisited Array 去记录 number of nodes passed since start
若 cycle 闭合，则 number of nodes passed so far 及为我们想要的包含 target node 的最小 cycle
Code
```
import java.util.*;
```

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

    // BFS_Initialization
    Queue<Integer> q = new LinkedList<>();
    int n = graph.length; // Number of nodes
    // Record the # of nodes that has been visited
    int[] hasVisited = new int[n];
    for (int i=0; i<graph.length; i++) { hasVisited[i] = 0;}
    // BFS starts from target node, to see if we can get back
    q.offer(target);
    hasVisited[target] = 1;

    // BFS
    while (!q.isEmpty()){
        int cur = q.poll();
        // Explore the neighbors
        for (int adjac: graph[cur]) {
            // Reach cycle
            if (adjac == target) {
                // Return the # of nodes have been visited in cycle
                return hasVisited[cur];
            }
            // Keep going if not visited yet
            if (hasVisited[adjac] == 0) {
                q.offer(adjac);
                hasVisited[adjac] = hasVisited[cur] + 1;
            }
        }
    }
    // No cycle closed, return -1
    return -1;
}

}


# Complexity
- Time: O(n)
- Space: O(n)

xingchen77 commented 2 years ago

打卡

    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

Geek-LX commented 2 years ago

5.22

思路：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)

carterrr commented 2 years ago

import java.util.*;

class Solution {

public int solve(int[][] graph, int target) {
   // from target,find next until target by bfs
    // save the steps, return steps first if find the target  or return -1 at the end 
    // step incr in every round

    int step = 0;
    Queue<Integer> q = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();
    q.offer(target);
    while(!q.isEmpty()){
        int size = q.size();
        for(int i = 0; i < size; i++) {
            Integer cur = q.poll();
            for(int c : graph[cur]) {
                if(c == target) {
                    return step +1 ;
                }
                if(!visited.contains(c)) { // 没访问过就加入下次访问集合 访问过说明之前已经找了这个点的后继  路径肯定比现在再访问短
                    q.offer(c);
                    visited.add(c);
                }
        }
        }

        step ++; // 一个size 才加一次
    }
    return -1;
}

}

houmk1212 commented 2 years ago

思路

BFS；从target开始搜索，找到能回到target的最小长度；

代码

import java.util.*;

class Solution {
    boolean[] visit;
    int res = Integer.MAX_VALUE;

    public int solve(int[][] graph, int target) {
        int m = graph.length;
        visit = new boolean[m];

        return bfs(graph, target, target);
    }

    public int bfs(int[][] graph, int target, int cur) {
        int m = graph.length;
        Deque<Integer> queue = new ArrayDeque<>();
        int len = 0;
        for (int next : graph[cur]) {
            visit[next] = true;
            queue.offer(next);
        }
        while (!queue.isEmpty()) {
            len++;
            int num = queue.size();
            for (int i = 0; i < num; i++) {
                int tmpcur = queue.pop();
                if (tmpcur == target) {
                    return len;
                }
                for (int next : graph[tmpcur]) {
                    if (!visit[next]){
                        visit[next] = true;
                        queue.offer(next);
                    }
                }
            }
        }
        return -1;
    }
}

复杂度

时间复杂度：O（V+E）
空间复杂度：O（V）

currybeefer commented 2 years ago

参考的答案，先记录，之后有时间慢慢看

int solve(vector<vector<int>>& graph, int target) 
{
    queue<int> q;
    vector<bool> visited(graph.size(), false);
    for (int &v : graph[target]) q.push(v);
    int res = 0;
    while (!q.empty()) 
    {
        int sz = q.size();
        res++;
        for (int i = 0; i < sz; i++) 
        {
            int v = q.front();
            q.pop();
            visited[v] = true;
            if (v == target) return res;
            for (int &u : graph[v]) 
            {
                if (!visited[u]) q.push(u);
            }
        }
    }
    return -1;
}

gitbingsun commented 2 years ago

include

int solve(vector<vector>& graph, int target) { vector visited(graph.size(), 0); queue q; if (graph.size() < target) return -1;

q.push(target); // start from target

// bsf int len = 0; while (!q.empty()) { for (int i= 0; i < q.size(); i++) { int cur = q.front(); q.pop(); cout << cur <<" visted, len:" << len<< endl; visited[cur] = 1; for (auto v : graph[cur]) { cout<<"v:"<<v<<endl; if (visited[v]== 0) q.push(v); else if (v == target) { return len+1; } } } len++; }

return -1;

}

Ellie-Wu05 commented 2 years ago

学习官方题解

'''

class Solution:

def solve(self, graph, target):

    q = collections.deque([target])

    visited = set()

    ans= 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 ans + 1
        ans +=1

    return -1

'''

ShuqianYang commented 2 years ago


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

zhiyuanpeng commented 2 years ago

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

time O(v+e) space O(V)

xil324 commented 2 years ago

class Solution:
    def solve(self, graph, target):
        if not graph: 
            return -1; 
        queue = collections.deque();
        queue.append(target); 
        visited = set();
        visited.add(target); 
        ans = 0;
        while queue:
            ans += 1;
            for _ in range(len(queue)):
                curr = queue.popleft();
                for nextNode in graph[curr]:
                    if nextNode == target:
                        return ans; 
                    else:
                        if nextNode not in visited:
                            visited.add(nextNode);
                            queue.append(nextNode); 
        return -1;

zzz607 commented 2 years ago

思路

抄的，因为最近在学习工作流，时间基本都花在这上面了

代码

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

复杂度分析

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

yinhaoti commented 2 years ago

class Solution:
    def solve(self, graph, target):
        """
        bfs
        TC: O(v+e)
        SC: O(v)
        """
        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

antmUp commented 2 years ago

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

ShawYuan97 commented 2 years ago

思路

首先找到target，从target开始反向搜索，层序信息就可以记录环的大小

关键点

使用带有层信息的BFS

代码

class Solution:
def solve(self, graph, target):
    """
    找到包含目标正数的环 然后求出长度最小的环的长度
    """
    deque = collections.deque([target])
    step = 0
    visited = set()
    while deque:
        for _ in range(len(deque)):
            cur = deque.popleft()
            visited.add(cur)
            for neighbor in graph[cur]:
                if neighbor not in visited:
                    deque.append(neighbor)
                elif neighbor == target:
                    return step + 1
        step += 1
    return -1

复杂度

令 v 节点数, e 为边数。时间复杂度：$ O(v+e) $ 空间复杂度：$ O(v) $

Shuchunyu commented 2 years ago

import java.util.*;

class Solution { boolean[] visit; int res = Integer.MAX_VALUE;

public int solve(int[][] graph, int target) {
    int m = graph.length;
    visit = new boolean[m];

    return bfs(graph, target, target);
}

public int bfs(int[][] graph, int target, int cur) {
    int m = graph.length;
    Deque<Integer> queue = new ArrayDeque<>();
    int len = 0;
    for (int next : graph[cur]) {
        visit[next] = true;
        queue.offer(next);
    }
    while (!queue.isEmpty()) {
        len++;
        int num = queue.size();
        for (int i = 0; i < num; i++) {
            int tmpcur = queue.pop();
            if (tmpcur == target) {
                return len;
            }
            for (int next : graph[tmpcur]) {
                if (!visit[next]){
                    visit[next] = true;
                    queue.offer(next);
                }
            }
        }
    }
    return -1;
}

}

xiayuhui231 commented 2 years ago

代码

int solve(vector<vector<int>>& graph, int target) 
{
    queue<int> q;
    vector<bool> visited(graph.size(), false);
    for (int &v : graph[target]) q.push(v);
    int res = 0;
    while (!q.empty()) 
    {
        int sz = q.size();
        res++;
        for (int i = 0; i < sz; i++) 
        {
            int v = q.front();
            q.pop();
            visited[v] = true;
            if (v == target) return res;
            for (int &u : graph[v]) 
            {
                if (!visited[u]) q.push(u);
            }
        }
    }
    return -1;
}

LQyt2012 commented 2 years ago

思路

BFS

代码

class Solution:
    def solve(self, graph, target):
        """
        找到包含目标正数的环 然后求出长度最小的环的长度
        """
        deque = collections.deque([target])
        step = 0
        visited = set()
        while deque:
            for _ in range(len(deque)):
                cur = deque.popleft()
                visited.add(cur)
                for neighbor in graph[cur]:
                    if neighbor not in visited:
                        deque.append(neighbor)
                    elif neighbor == target:
                        return step + 1
            step += 1
        return -1

复杂度分析

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

freedom0123 commented 2 years ago

int solve(vector<vector<int>>& graph, int target) 
{
    queue<int> q;
    vector<bool> visited(graph.size(), false);
    for (int &v : graph[target]) q.push(v);
    int res = 0;
    while (!q.empty()) 
    {
        int sz = q.size();
        res++;
        for (int i = 0; i < sz; i++) 
        {
            int v = q.front();
            q.pop();
            visited[v] = true;
            if (v == target) return res;
            for (int &u : graph[v]) 
            {
                if (!visited[u]) q.push(u);
            }
        }
    }
    return -1;
}

miss1 commented 2 years ago

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

zhishinaigai commented 2 years ago


vector<int> color;
vector<long long int> dist;
vector<vector<int>> adj;
int dest;
long long int dfs(int u) {
    if (u == dest) {
        return 0;
    }
    color[u] = 1;  // gray
    long long int mindist = INT_MAX;
    for (int v : adj[u]) {
        if (color[v] == 0) {
            mindist = min(mindist, 1 + dfs(v));
        } else if (color[v] == 2) {
            mindist = min(mindist, 1 + dist[v]);
        }
    }
    color[u] = 2;  // black
    return dist[u] = mindist;
}

int solve(vector<vector<int>>& graph, int target) {
    adj = graph;
    dest = target;
    color.assign(graph.size(), 0);
    dist.assign(graph.size(), 0);
    long long int res = INT_MAX;
    for (int i : graph[target]) {
        res = min(res, 1 + dfs(i));
    }
    if (res == INT_MAX) return -1;
    return res;
}

Orangejuz commented 2 years ago

class Solution:
    def solve(self, graph, target):
        seen = set()
        if target <0 or target>=len(graph):
            return -1
        stack = collections.deque()
        stack.append(target)
        ans = 1
        while stack:
            l = len(stack)
            for _ in range(l):
                cur = stack.popleft()
                if cur not in seen:
                    seen.add(cur)
                    for nei in graph[cur]:
                        if nei == target:
                            return ans
                        else:
                            if nei not in seen:
                                stack.append(nei)
            ans += 1
        return -1

revisegoal commented 2 years ago

bfs

从target点开始bfs，每个顶点都遍历其邻接顶点，若邻接顶点没遍历过则加入队列，如果其等于target则说明已经绕了一圈，返回记录步骤值 + 1，即环的长度

import java.util.*;

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

time: O(v + e)
space: O(v)

AConcert commented 2 years ago

def solve(self, graph, target):
    q = collections.deque([target])
    visited = set()
    ans= 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 ans + 1
        ans +=1
    return -1

taojin1992 commented 2 years ago

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

wychmod commented 2 years ago

思路

bfs 想明白bfs的层数就是返回值就做出来了

代码

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

ShirAdaOne commented 2 years ago

代码

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

maggiexie00 commented 2 years ago

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

flyzenr commented 2 years ago

代码

3```python class Solution: def solve(self, graph, target):

target入列

    q = collections.deque([target])
    # 初始化visit列表
    visited = set()
    初始化遍历层数
    steps = 0
    while q:
        for i in range(len(q)):
            # 弹出当前队首
            cur = q.popleft()
            # 将弹出的队首加入visited
            visited.add(cur)
            # 判断当前的元素是否在visited里面，如果在，记录steps
            for neighbor in graph[cur]:
                if neighbor not in visited:
                    q.append(neighbor)
                elif neighbor == target:
                    return steps + 1
        steps += 1
    return -1

```

gitbingsun commented 2 years ago

include

int solve(vector<vector>& graph, int target) { vector visited(graph.size(), 0); queue q; if (graph.size() < target) return -1;

q.push(target); // start from target

// bfs int len; len=0; while (!q.empty()) { int size = q.size(); for (int i= 0; i < size; i++) { int cur = q.front(); q.pop(); visited[cur] = 1; for (auto v : graph[cur]) { if (visited[v]== 0) q.push(v); else if (v == target) { return len+1; } } } len++; }

return -1;

}

weihaoxie commented 2 years ago

思路

从目标开始进行BFS，用visited记录访问过的节点，如果再次遇到则为包含目标的最短环

代码

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)

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

【Day 52 】2022-05-22 - Shortest-Cycle-Containing-Target-Node #57

Shortest-Cycle-Containing-Target-Node

入选理由

题目地址

前置知识

题目描述

Idea:

Code:

Complexity:

C++

Idea

Code

打卡

5.22

思路

代码

复杂度

include

include

include

思路

代码

思路

关键点

代码

复杂度

代码

思路

代码

复杂度分析

bfs

思路

代码

代码

代码

target入列

```

include

include

include

思路

代码

复杂度