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

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

图的遍历

题目描述

给出

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\%$
• 对于 $100\%$

题解代码

学会利用新知，自己多试试并尝试积攒一些固定解答方案，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后成功编译并运行出正确结果真的会感到很幸福！

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

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

代码007普通

打赏 收藏 海报 链接