[洛谷春令营 D7T1] 图的遍历【Tarjan缩点+记忆化搜索】
题目描述
给出 个点, 条边的有向图,对于每个点 ,求 表示从点 出发,能到达的编号最大的点。
输入输出格式
输入格式:
第 1 行,2 个整数 。
接下来 行,每行 2 个整数 ,表示边 。点用 编号。
输出格式:
N 个整数 。
输入输出样例
输入样例#1:
4 3 1 2 2 4 4 3
输出样例#1:
4 4 3 4
说明
• 对于 60% 的数据,;
• 对于 100% 的数据,。
Solution:
这是一道 比较水的 图论题。
第一思路是记忆化搜索,理论复杂度 O(N)。
然而我们发现,记忆化搜索可以看作动规,只能在 DAG 上进行。
而本题并未保证给出的有向图无环,所以需要先用 Tarjan 缩点。
Code: O(N+M) [9054K, 92MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; inline void getint(int &num){ char ch; while(!isdigit(ch = getchar())); num = ch - '0'; while(isdigit(ch = getchar())) num = num * 10 + ch - '0'; } int N, M; struct Edge{ int np; Edge *nxt; }; struct Graph{ Edge E[100005], *V[100005]; int tope; inline void addedge(int u, int v){ E[++tope].np = v; E[tope].nxt = V[u], V[u] = &E[tope]; } } G, C; int dfn[100005], dfstime = 0, low[100005]; int stk[100005], tops = 0, stat[100005]; int col[100005], topc = 0; inline void Tarjan(int u){ low[u] = dfn[u] = ++dfstime; stk[++tops] = u, stat[u] = 1; for(register Edge *ne = G.V[u]; ne; ne = ne->nxt){ if(stat[ne->np] == 0){ Tarjan(ne->np); low[u] = min(low[u], low[ne->np]); } else if(stat[ne->np] == 1) low[u] = min(low[u], dfn[ne->np]); } if(low[u] == dfn[u]){ topc++; while(stk[tops + 1] != u){ col[stk[tops]] = topc; stat[stk[tops--]] = 2; } } } int mxid[100005], A[100005]; inline int dfs(int u){ if(A[u]) return A[u]; A[u] = mxid[u]; for(register Edge *ne = C.V[u]; ne; ne = ne->nxt) A[u] = max(A[u], dfs(ne->np)); return A[u]; } int main(){ getint(N), getint(M); for(register int i = 1; i <= M; i++){ int u, v; getint(u), getint(v), G.addedge(u, v); } for(register int i = 1; i <= N; i++) if(stat[i] == 0) Tarjan(i); for(register int i = 1; i <= N; i++){ mxid[col[i]] = max(mxid[col[i]], i); for(register Edge *ne = G.V[i]; ne; ne = ne->nxt) C.addedge(col[i], col[ne->np]); } memset(stat, 0, sizeof(stat)); for(register int i = 1; i <= N; i++) if(stat[i] == 0) dfs(i); for(register int i = 1; i < N; i++) printf("%d ", A[col[i]]); printf("%d\n", A[col[N]]); return 0; }
发表评论