自动搬运

查看原文

来自洛谷，原作者为

	Base_ring_tree 代词使用杝，代词使用杝，代词使用杝，代词使用杝||这个家伙很懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒懒

搬运于2025-08-24 21:15:33，当前版本为作者最后更新于2023-10-09 17:33:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

蒟蒻第一次发题解，望审核通过

题目

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

这是一道图的遍历考察的是如何使用 DFS 遍历图（废话）。

思路

我们可以来这样思考，我们按节点编号大小从大到小依此遍历每一个数所能到达的节点，这一个操作可以用 DFS。

再来详细的说如何 DFS。

我们可以反向建边，这样如果一个点 $x$ 能被另一个点 $y$ 访问到，那么 $x$ 也一定能访问 $y$。

DFS 的过程就是：如果我遍历到一个点 $x$ 就来看这个点是否被比我编号更大的点访问过。

简单点说就是看 $x$ 是否被标记过。我们是按节点编号大小从大到小依此遍历，如果 $x$ 被标记过就是说明 $x$ 被比我编号更大的点访问过。

如果没有那么就表明我是 $x$ 可以访问到的编号最大的点（这样就可以知道 $x$ 多能到达最大的节点的编号了）。

然后再依次 DFS 自己的子节点就好惹！

代码！

注释较少，别打我...

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

#define TRACE 1
#define tcout TRACE && cout

#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define int long long

#ifdef int
const int INF = 0x3f3f3f3f3f3f3f3f; 
#else
const int INF = 0x3f3f3f3f;
#endif

const int P = 998244353; 
const int N = 1e5 + 10, M = 1e5 + 10; 

int n, m;
vector<int> g[N];

bool vis[N];

int a[N];

void dfs(int u, int i)
{
	if(vis[u])
	{
		//如果这个点被别的点到达过, 则不能再走了
		return;
	}
	vis[u] = 1;
	a[u] = i;
	for(auto v: g[u])
	{
		if(vis[v] == 0)
		{
			dfs(v, i);
		}
	}
}

signed main()
{
	cin >> n >> m;
	for(int i=1; i<=m; i++)
	{
		int u, v;
		cin >> u >> v;
		g[v].push_back(u);
	}
	for(int i=n; i>=1; i--)
	{
		dfs(i, i);	//从i点出发, 能到哪个点, 就表示哪个点能到i
	}
	for(int i=1; i<=n; i++)
	{
		cout << a[i] << " ";
	}
	return 0;
}