洛谷 2921 记忆化搜索 tarjan
()
做这题的经历有点玄学,,起因是某个random题的同学突然发现了一个0提交0通过的题目,然后就引发了整个机房的兴趣,,然后,,就变成了16提交7通过,,
初看上去这题目就是记忆化搜索,但是环的存在使得普通的记忆化会导致漏解,继续观察发现整张图为n个点n条边,即是多个基环外向树,使用tarjan找到图中的环,显然可知,对于环上一点,能取到的最大值是环的长度,对于环外一点,能取到的最大值是它走到环的长度加上环长,之后采用记忆化搜索或dp即可得解
Warning:
- 从样例可以显然发现,存在自环
- 开始写tarjan时错误的理解了low数组的含义,将其与from数组混淆
#include#include #include const int maxn = 100000 + 100;int next[maxn];int dfn[maxn], low[maxn], size[maxn], sta[maxn];int from[maxn];int vis[maxn];int stackTop = 0;int tim = 0;int n;int ans[maxn];void tarjan(int x) { tim++; stackTop++; sta[stackTop] = x; dfn[x] = low[x] = tim; vis[x] = 1; if (!dfn[next[x]]) { tarjan(next[x]); low[x] = std :: min(low[next[x]], low[x]); } else if (vis[next[x]]) { low[x] = std :: min(low[x], dfn[next[x]]); } if (low[x] == dfn[x]) { while (sta[stackTop] != x) { size[x]++; from[sta[stackTop]] = x; vis[sta[stackTop]] = 0; stackTop--; } vis[x] = 0; stackTop--; size[x]++; from[x] = x; }}void dfs(int x) { if (ans[x] > 0) return; if (from[x] != x || size[x] > 1) { ans[x] = size[from[x]]; return; } else if (next[x] == x) { ans[x] = 1; return; } else { dfs(next[x]); ans[x] = 1 + ans[next[x]]; }}int main () { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &next[i]); } for (int i = 1; i <= n; i++) { if (!dfn[i]) tarjan(i); } //for (int i = 1; i <= n; i++) // printf("%d\n", from[i]); for (int i = 1; i <= n; i++) if (ans[i] == 0) dfs(i); for (int i = 1; i <= n; i++) printf("%d\n", ans[i]); return 0;}