中文网站模板下载免费,交换链接营销的典型案例,wordpress 对外请求,企业网站建设案例洛谷 2921 记忆化搜索 tarjan 传送门 (https://www.luogu.org/problem/show?pid2921) 做这题的经历有点玄学#xff0c;#xff0c;起因是某个random题的同学突然发现了一个0提交0通过的题目#xff0c;然后就引发了整个机房的兴趣#xff0c;#xff0c;然后#xff0c… 洛谷 2921 记忆化搜索 tarjan 传送门 (https://www.luogu.org/problem/show?pid2921) 做这题的经历有点玄学起因是某个random题的同学突然发现了一个0提交0通过的题目然后就引发了整个机房的兴趣然后就变成了16提交7通过 初看上去这题目就是记忆化搜索但是环的存在使得普通的记忆化会导致漏解继续观察发现整张图为n个点n条边即是多个基环外向树使用tarjan找到图中的环显然可知对于环上一点能取到的最大值是环的长度对于环外一点能取到的最大值是它走到环的长度加上环长之后采用记忆化搜索或dp即可得解 Warning: 从样例可以显然发现存在自环开始写tarjan时错误的理解了low数组的含义将其与from数组混淆 #include cstdio
#include cstring
#include algorithmconst 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;
}转载于:https://www.cnblogs.com/CtsNevermore/p/6018135.html
