图的遍历
题目描述
给出 $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)$。
样例 #1
样例输入 #1
4 3
1 2
2 4
4 3
样例输出 #1
4 4 3 4
提示
- 对于 $60\%$ 的数据,$1 \leq N,M \leq 10^3$。
- 对于 $100\%$ 的数据,$1 \leq N,M \leq 10^5$。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010;
int n,m;
int h[N],e[N],ne[N],idx;
int res[N];
bool st[N];
void add(int a,int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++ ;
}
void dfs(int u,int end)
{
st[u] = true;
res[u] = end;
for(int i = h[u];i != -1;i = ne[i])
{
int j = e[i];
if(!st[j])
dfs(j,end);
}
}
int main()
{
cin >> n >> m;
memset(h,-1,sizeof h);
for(int i = 1;i <= m;i ++)
{
int a,b;
cin >> a >> b;
add(b,a);
}
for(int i = n;i >= 1;i --)
if(!st[i])
dfs(i,i);
for(int i = 1;i <= n;i ++)
cout << res[i] << " ";
return 0;
}