Shortest Cycle Containing Target Node#

1
You are given a two-dimensional list of integers graph
2

3
representing a directed graph as an adjacency list.
4

5
You are also given an integer target.
6

7
Return the length of a shortest cycle that contains target.
8

9
If a solution does not exist, return -1.
10

11
Constraints
12

13
n, m ≤ 250 where n and m are the number of rows and columns in graph
14
Example 1
15
Input
16
Visualize
17
graph = [
18
    [1],
19
    [2],
20
    [0]
21
]
22
target = 0
23
Output
24
3
25
Explanation
26
The nodes 0 -> 1 -> 2 -> 0 form a cycle
27

28
Example 2
29
Input
30
Visualize
31
graph = [
32
    [1],
33
    [2],
34
    [4],
35
    [],
36
    [0]
37
]
38
target = 3
39
Output
40
-1

1
int solve(vector<vector<int>>& g, int t) {
2
    int n = g.size();
3
    vector<bool> vis(n, 0);
4
    queue<int> q;
5
    q.push(t);
6
    int ans = 0;
7

8
    while (!q.empty())
9
    {
10
        ans++;
11
        int n = q.size();
12
        for (int i = 0; i < n; i++)
13
        {
14
            int node = q.front();q.pop();
15
            for (auto& v : g[node])
16
            {
17
                if(v == t) return ans;
18
                if(!vis[v])  //如果是未访问节点， 等价于 vis[v] == 0
19
                {
20
                    q.push(v);
21
                    vis[v] = 1;
22
                }
23
            }
24
        }
25
    }
26
    return -1;
27
}