题目描述

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

输入格式

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

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

输出格式

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

解题思路：一种简单粗暴的算法是从每个点搜索能到达的点，再找出最大的，然而这种暴搜的时间复杂度接近O(n^2)，过十万似乎只能是奇迹，于是我们应该换一下思路：按每个点可以到达最大点的编号，不如考虑较大的点能到达哪些点，于是就会很自然地想到应该反向建边，从大到小遍历。

代码部分：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const int N = 100010; int n, m;
int h[N], e[N], ne[N], idx;
int ans[N];void add(int a, int b)//建立一条边a->b 
{e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}void dfs(int u,int v)
{ if(ans[u]) return;ans[u] = v;for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i];dfs(j,v);}}int read()
{int t = 0, f = 1;char ch = getchar();while(ch > '9' || ch < '0') {if(ch == '-') f = -1;ch = getchar();}while(ch <= '9' && ch >= '0') {t = t * 10 + ch - '0';ch = getchar();}return t * f;
} int main()
{n = read();  // 读取节点数m = read();  // 读取边数memset(h, -1, sizeof(h));  // 初始化邻接表数组while(m--) {int a = read(), b = read();  // 读取每条边的两个端点add(b, a);  // 将边添加到邻接表中}for(int i = n; i >= 1; i--) {dfs(i,i);  // 对每个节点执行深度优先搜索}for(int i=1; i<=n; i++) cout<<ans[i]<<' ';return 0;
}