题目描述：
现有一个有向图，其中包含 n 个节点，节点编号从 0 到 n - 1 。此外，该图还包含了 n 条有向边。
给你一个下标从 0 开始的数组 edges ，其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的边。
想象在图上发生以下过程：
- 你从节点
x 开始，通过边访问其他节点，直到你在 此过程 中再次访问到之前已经访问过的节点。
返回数组 answer 作为答案，其中 answer[i] 表示如果从节点 i 开始执行该过程，你可以访问到的不同节点数。
数据范围：
$2\le n \le 10^5$
无自环。
题解：
首先， $i\rightarrow edges[i]$ 表示每个点只有一个出边。并且 $n$ 个点， $n$ 条边，是一棵基环树。
由于每个点只有一个出边，基环外面的点都是指向基环的，即内向基环树。
由于不一定是连通的，可能是基环树森林。
环上的点，答案是环的大小，环外的点，答案是深度加环的大小。
可以直接先 dfs 求出来环的大小，然后将环上的点更新答案。
然后可以从环上的点对不在环上的点反图 $dfs$ ，求出来每个节点的深度。
也可以直接正向dfs，每次遇到已经填过答案的返回。
之前没发现是基环树，而且没有发现每个点只有一个出边。想成了一般的有向图，先缩点，再拓扑排序，然后再使用 $bitset$ 进行 $dp$ ，类似164. 可达性统计 | Luobuyu’s Blog
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
vector<vector<int>> g, rg;
vector<int> vis;
vector<int> ans;
vector<int> dfn;
int dfn_clock = 0;
vector<int> st;
int top = -1;
void dfs(int u)
{
vis[u] = 1;
dfn[u] = ++dfn_clock;
st[++top] = u;
for (int i = 0; i < g[u].size(); ++i)
{
int v = g[u][i];
if (vis[v] == 1)
{
int size = dfn[u] - dfn[v] + 1;
while (true)
{
ans[st[top]] = size;
if (st[top] == v)
break;
--top;
}
}
else if (vis[v] == 0)
{
dfs(v);
}
}
vis[u] = 2;
}
int dfs2(int u)
{
if (ans[u])
return ans[u];
for (int i = 0; i < g[u].size(); ++i)
{
int v = g[u][i];
ans[u] = dfs2(v) + 1;
}
return ans[u];
}
vector<int> countVisitedNodes(vector<int> &edges)
{
int n = edges.size();
g.resize(n), rg.resize(n);
dfn.resize(n), ans.resize(n);
vis.resize(n);
st.resize(n);
for (int i = 0; i < n; ++i)
{
int u = i, v = edges[i];
g[u].emplace_back(v);
rg[v].emplace_back(u);
}
for (int i = 0; i < n; ++i)
{
if (!dfn[i])
dfs(i);
}
for (int i = 0; i < n; ++i)
{
if (!ans[i])
{
dfs2(i);
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
vector<vector<int>> g, rg;
vector<int> indeg;
vector<int> ans;
void dfs(int u, vector<int> &ring)
{
ring.emplace_back(u);
indeg[u] = -1;
for (int i = 0; i < g[u].size(); ++i)
{
int v = g[u][i];
if (indeg[v] == 1)
dfs(v, ring);
}
}
void dfs2(int u)
{
for (int i = 0; i < rg[u].size(); ++i)
{
int v = rg[u][i];
if (indeg[v] == 0)
{
ans[v] = ans[u] + 1;
dfs2(v);
}
}
}
vector<int> countVisitedNodes(vector<int> &edges)
{
int n = edges.size();
g.resize(n), rg.resize(n);
indeg.resize(n), ans.resize(n);
for (int i = 0; i < n; ++i)
{
int u = i, v = edges[i];
g[u].emplace_back(v);
rg[v].emplace_back(u);
indeg[v]++;
}
queue<int> q;
for (int i = 0; i < n; ++i)
{
if (indeg[i] == 0)
q.push(i);
}
while (q.size())
{
int u = q.front();
q.pop();
for (int i = 0; i < g[u].size(); ++i)
{
int v = g[u][i];
indeg[v]--;
if (indeg[v] == 0)
{
q.push(v);
}
}
}
for (int i = 0; i < n; ++i)
{
if (indeg[i] == 1)
{
vector<int> ring;
dfs(i, ring);
int size = ring.size();
for (auto &u : ring)
{
ans[u] = size;
dfs2(u);
}
}
}
return ans;
}
};
|