【备战蓝桥杯】图的遍历问题

蓝桥杯备赛 | 洛谷做题打卡day10

文章目录 蓝桥杯备赛 | 洛谷做题打卡day10图的遍历题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示题解代码我的一些话

图的遍历 题目描述

给出 N N N 个点， M M M 条边的有向图，对于每个点 v v v，求 A ( v ) A(v) A(v) 表示从点 v v v 出发，能到达的编号最大的点。

输入格式

第 1 1 1 行 2 2 2 个整数 N , M N,M N,M，表示点数和边数。

接下来 M M M 行，每行 2 2 2 个整数 U i , V i U_i,V_i Ui​,Vi​，表示边 ( U i , V i ) (U_i,V_i) (Ui​,Vi​)。点用 1 , 2 , … , N 1,2,\dots,N 1,2,…,N 编号。

输出格式

一行 N N N 个整数 A ( 1 ) , A ( 2 ) , … , A ( N ) A(1),A(2),\dots,A(N) A(1),A(2),…,A(N)。

样例 #1 样例输入 #1 4 3 1 2 2 4 4 3 样例输出 #1 4 4 3 4 提示 对于 60 % 60\% 60% 的数据， 1 ≤ N , M ≤ 1 0 3 1 \leq N,M \leq 10^3 1≤N,M≤103。对于 100 % 100\% 100% 的数据， 1 ≤ N , M ≤ 1 0 5 1 \leq N,M \leq 10^5 1≤N,M≤105。 题解代码

学会利用新知，自己多试试并尝试积攒一些固定解答方案，debug，以下是题解代码 ~

#include <iostream> #include <cstdio> #include <vector> using namespace std; #define MAXL 100010 int N, M, A[MAXL]; vector<int> G[MAXL]; //vector存图 void dfs(int x, int d) { if(A[x]) return; //访问过 A[x] = d; for(int i=0; i<G[x].size(); i++) dfs(G[x][i], d); } int main() { int u, v; scanf("%d%d", &N, &M); for(int i=1; i<=M; i++) { scanf("%d%d", &u, &v); G[v].push_back(u); //反向建边 } for(int i=N; i; i--) dfs(i, i); for(int i=1; i<=N; i++) printf("%d ", A[i]); printf("\n"); return 0; } 我的一些话

今天给大家复习一下前几天初步入门的图论算法，关于图的遍历确实有一定难度，需要通盘的考虑和理解，以及扎实的数据结构基础才能独立写出AC代码。但无论难易，大家都要持续做题，保持题感喔！一起坚持(o´ω`o)

如果有非计算机专业的uu自学的话，关于数据结构的网课推荐看b站上青岛大学王卓老师的课，讲的很细致，有不懂都可以私信我喔

总结来说思路很重要，多想想，多在草稿纸上画画，用测试数据多调试，debug后成功编译并运行出正确结果真的会感到很幸福！

关于之前蓝桥杯备赛的路线和基本方法、要掌握的知识，之前的博文我都有写，欢迎大家关注我，翻阅自取哦~

不管什么都要坚持吧，三天打鱼两天晒网无法形成肌肉记忆和做题思维，该思考的时候一定不要懈怠，今天就说这么多啦，欢迎评论留言，一起成长：）