【题目来源】
洛谷：P3916 图的遍历 - 洛谷
【题目描述】
给出 \(N\) 个点，\(M\) 条边的有向图，对于每个点 \(v\)，求 \(A(v)\) 表示从点 \(v\) 出发，能到达的编号最大的点。
【输入】
第 \(1\) 行 \(2\) 个整数 \(N,M\)，表示点数和边数。
接下来 \(M\) 行，每行 \(2\) 个整数 \(U_i,V_i\)，表示边 \((U_i,V_i)\)。点用 \(1,2,\dots,N\) 编号。
【输出】
一行 \(N\) 个整数 \(A(1),A(2),\dots,A(N)\)。
【输入样例】
4 3
1 2
2 4
4 3
【输出样例】
4 4 3 4
【解题思路】
【算法标签】
《洛谷 P3916 图的遍历》 #搜索# #图论# #图论建模# #强连通分量#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
struct d { // 定义每个点的结构体vector<int> cdd; // 每个点的邻接点int ad; // 到达的编号最大的点
};
int main()
{int n, m, ls1, ls2, nls;queue<d> que;cin >> n >> m; // 输入n和md ds[n+1]; // 定义结构体数组for (int i=1; i<=n; i++) { // for循环遍历所有点ds[i].ad = i; // 每个点初始可到达的编号最大的点都是自己}for (int i=0; i<m; i++) { // for循环遍历m条边cin >> ls1 >> ls2; // 输入起始点和终止点ds[ls2].cdd.push_back(ls1); // 反向存储，终止点可以到达的起始点}for (int i=n; i>0; i--) { // 从最后一个点开始往前遍历que.push(ds[i]); // 将这个点放入队列中while (que.size()) { // 当队列不为空for (int j=0; j<que.front().cdd.size(); j++) { // 遍历该点可到达的所有点nls = que.front().cdd[j]; // 获得i的邻接点，赋值给nlsif (ds[nls].ad == nls && ds[nls].ad < i) { // 如果该邻接点nls的可到达编号最大的点为自己（没有修改过），且小于当前点i（即存在比i小的，且nls可以到达的点）ds[nls].ad = i; // 则该点的邻接点nls的可到达的编号最大的点就是ique.push(ds[nls]); // 将该点的邻接点压入队列}}que.pop();}}for (int i=1; i<=n; i++) {cout << ds[i].ad << " ";}cout << endl;return 0;
}
【运行结果】
4 3
1 2
2 4
4 3
4 4 3 4