题目描述
给出 $N$ 个点， $M$ 条边的有向图，对于每个点 $v$ ，求 $A(v)$ 表示从点 $v$ 出发，能到达的编号最大的点。
输入输出格式
输入格式：
第1 行，2 个整数 $N,M$ 。
接下来 $M$ 行，每行2个整数 $U_i,V_i$ ，表示边 $(U_i,V_i)$ 。点用 $1, 2,\cdots,N$ 编号。
输出格式：
$N$ 个整数 $A(1),A(2),\cdots,A(N)$ 。
输入输出样例
输入样例#1：4 31 22 44 3输出样例#1：4 4 3 4说明
• 对于60% 的数据， $1 \le N . K \le 10^3$ ；
• 对于100% 的数据， $1 \le N , M \le 10^5$ 。
有部分分，那就先打个暴力。
#include <iostream> #include <cstring> #include <cstdio> #define Edge_max 100008 using namespace std; int n, m, outdgr[Edge_max], ans; bool vis[Edge_max]; int u[Edge_max], v[Edge_max], first[Edge_max], next[Edge_max]; void dfs(int k) { ans = max(ans, k); if(outdgr[k] == 0) { return ; } int s = first[k]; while(s != -1) { if(!vis[v[s]]) { vis[v[s]] = 1; dfs(v[s]); vis[v[s]] = 0; } s = next[s]; } } int main() { scanf("%d%d", &n, &m); memset(first, -1, sizeof(first)); for(int i=1; i<=m; i++) { scanf("%d%d", &u[i], &v[i]); next[i] = first[u[i]]; first[u[i]] = i; outdgr[u[i]]++; } for(int i=1; i<=n; i++) { memset(vis, 0, sizeof(vis)); ans = 0; dfs(i); printf("%d ", ans); } }
铛啷啷，就是这样的。
然后我们考虑反向建边，这样就不会有后效性。
然后把沿途经过的点都标记一遍，就$AC$了
#include <iostream> #include <cstring> #include <cstdio> #define Edge_max 100008 using namespace std; int n, m, ans, A[Edge_max]; bool vis[Edge_max]; int u[Edge_max], v[Edge_max], first[Edge_max], next[Edge_max]; void dfs(int k) { A[k] = max(A[k], k); int s = first[k]; while(s != -1) { if(!A[v[s]]) A[v[s]] = A[k], dfs(v[s]); s = next[s]; } } int main() { scanf("%d%d", &n, &m); memset(first, -1, sizeof(first)); for(int i=1; i<=m; i++) { scanf("%d%d", &u[i], &v[i]); swap(u[i], v[i]); next[i] = first[u[i]]; first[u[i]] = i; } for(int i=n; i>=1; i--) { ans = 0; dfs(i); } for(int i=1; i<=n; i++) printf("%d ", A[i]); return 0; }
转载于:https://www.cnblogs.com/bljfy/p/9053521.html
相关资源：数据结构—成绩单生成器