【Day 44 】2021-06-22 - Shortest-Cycle-Containing-Target-Node

题目描述

hortest-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

我的回答

解法一

时空复杂度

时间复杂度：O(n)

空间复杂度: O(n)

dfs

var findCircleNum = function (M) {
    let N = M.length
    const visited = Array(N).fill(0)
    let res = 0
    for (let i = 0; i < visited.length; i++) {
        if (!visited[i]) {
            visited[i] = 1
            dfs(i)
            res++
        }
    }
    return res
 
    function dfs(i) {
        for (let j = 0; j < N; j++) {
            // 不是自己，没有访问过，是朋友
            if (i !== j && !visited[j] && M[i][j]) {
                visited[j] = 1
                // 遍历J的朋友圈
                dfs(j)
            }
        }
    }
};

解法二

时空复杂度

时间复杂度：O(n)

空间复杂度: O(n)

并查集

参考回答