P3916 图的遍历 题解（反向建图）

更好的阅读体验博客园题面P3916 图的遍历题目描述给出N NN个点M MM条边的有向图对于每个点v vv令A ( v ) A(v)A(v)表示从点v vv出发能到达的编号最大的点。现在请求出A ( 1 ) , A ( 2 ) , … , A ( N ) A(1),A(2),\dots,A(N)A(1),A(2),…,A(N)的值。输入格式第1 11行2 22个整数N , M N,MN,M表示点数和边数。接下来M MM行每行2 22个整数U i , V i U_i,V_iUi​,Vi​表示边( U i , V i ) (U_i,V_i)(Ui​,Vi​)。点用1 , 2 , … , N 1,2,\dots,N1,2,…,N编号。输出格式一行N NN个整数A ( 1 ) , A ( 2 ) , … , A ( N ) A(1),A(2),\dots,A(N)A(1),A(2),…,A(N)。输入输出样例 #1输入 #14 3 1 2 2 4 4 3输出 #14 4 3 4说明/提示对于60 % 60\%60%的数据1 ≤ N , M ≤ 10 3 1 \leq N,M \leq 10^31≤N,M≤103。对于100 % 100\%100%的数据1 ≤ N , M ≤ 10 5 1 \leq N,M \leq 10^51≤N,M≤105。解析不难想到暴力做法dfs/bfs遍历每一个点得到对于它的最大值复杂度O ( n 2 ) O(n^2)O(n2)这是代码90 p t s 90pts90pts可以想到用时间戳解决多次m e m s e t ( ) memset()memset()的问题但是这样也依旧90 p t s 90pts90pts我们知道这是有向图这里就需要一个反向建图的做法反向建图把所有边的朝向反过来例如a - b, a - b有什么用呢不妨按照编号从大到小遍历节点则每一次能遍历到的之前没有被访问过的节点就一定和当前的出发节点相等因为后面即使遍历到了也不如这个大所以对于遍历过的节点直接在它这里r e t u r n returnreturn因为后面的节点一定也被访问过这样每个节点最多被访问一次复杂度O ( n ) O(n)O(n)AC代码#includebits/stdc.husingnamespacestd;constexprintN1e52;vectorinta[N];intvis[N];intb0;inlinevoiddfs(intnow){if(vis[now])return;vis[now]b;for(inti:a[now]){if(vis[i])continue;dfs(i);}}signedmain(){ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);intn,m;cinnm;for(inti1;im;i){intu,v;cinuv;a[v].push_back(u);}for(bn;b1;b--){dfs(b);}for(inti1;in;i){coutvis[i] ;}}该题解由deepseek审核如果对你有帮助的话请点个赞