題目描述
給出 N 個點，M 條邊的有向圖，對于每個點 v，求 A(v) 表示從點 v 出發(fā)，能到達的編號最大的點。

輸入格式
第 1 行 2 個整數(shù) N,M，表示點數(shù)和邊數(shù)。

接下來 M 行，每行 2 個整數(shù) Ui,Vi，表示一條從 Ui 到 Vi 的有向邊 (Ui,Vi)。點用 1,2,…,N 編號。

輸出格式
一行 N 個整數(shù) A(1),A(2),…,A(N)。

樣例 #1
樣例輸入 #1
4 3
1 2
2 4
4 3
樣例輸出 #1
4 4 3 4
提示
對于 60% 的數(shù)據(jù)，1≤N,M≤103。

對于 100% 的數(shù)據(jù)，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;
}