题目描述
给出 N 个点，M 条边的有向图，对于每个点 v，求 A(v) 表示从点 v 出发，能到达的编号最大的点。
输入格式
第 1 行 2 个整数 N,M，表示点数和边数。
接下来 M 行，每行 2 个整数 Ui,Vi，表示一条从 Ui 到 Vi 的有向边 (Ui,Vi)。点用 1,2,…,N 编号。
输出格式
一行 N 个整数 A(1),A(2),…,A(N)。
样例 #1
样例输入 #1
4 3
1 2
2 4
4 3
样例输出 #1
4 4 3 4
提示
对于 60% 的数据，1≤N,M≤103。
对于 100% 的数据，1≤N,M≤105。
#include<bits/stdc++.h>
using namespace std;
struct yjc {
int nxt;
int to;
int dis;
} yjc[100001];
int num;
int head[100001];
int n, m, ans;
bool vis[100001];
void add(int f, int to) {
num++;
yjc[num].to = to;
yjc[num].nxt = head[f];
head[f] = num;
}
void dfs(int i) {
if (vis[i] == true)return;
ans = max(i, ans);
vis[i] = true;
for (int j = head[i]; j != 0; j = yjc[j].nxt) {
int z = yjc[j].to;
if (!vis[z]) dfs(z);
}
}
void bfs(int i){
queue<int >q;
int start=i;
q.push(start);
vis[start]=1;
while(!q.empty()){
int now=q.front();
ans=max(ans,now);
if(ans==n)return;
q.pop();
for(int j=head[now];j!=0;j=yjc[j].nxt){
int w=yjc[j].to;
if(vis[w]==0) q.push(w),vis[w]=1;
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
add(x, y);
}
for (int j = 1; j < n; j++) {
ans = INT_MIN;
memset(vis, false, sizeof(vis));
bfs(j);
cout << ans << ' ';
}
cout<<n<<' ';
return 0;
}