Day 52 Shortest Cycle Containing Target Node

Shortest Cycle Containing Target Node

题目

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
Example 1
Input
Visualize
graph = [
    [1],
    [2],
    [0]
]
target = 0
Output
3
Explanation
The nodes 0 -> 1 -> 2 -> 0 form a cycle

Example 2
Input
Visualize
graph = [
    [1],
    [2],
    [4],
    [],
    [0]
]
target = 3
Output
-1

题目思路

• 1、BFS，查看其中的非可视化发现图的存储方式为邻接表，所以本题的图的 BFS 套用模板即可解决问题；
• 2、扫描整个图，然后判断每个节点跟目标 t 的关系，有直接 return true，最后找不到返回 false;

int solve(vector<vector<int>>& g, int t) {
    int n = g.size();
    vector<bool> vis(n, 0);
    queue<int> q;
    q.push(t);
    int ans = 0;

    while (!q.empty())
    {
        ans++;
        int n = q.size();
        for (int i = 0; i < n; i++)
        {
            int node = q.front();q.pop();
            for (auto& v : g[node])
            {
                if(v == t) return ans;
                if(!vis[v])  //如果是未访问节点， 等价于 vis[v] == 0
                {
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
    return -1;
}

复杂度

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

• 空间复杂度：O(n)