企业做网站的合同多页网站模板

题目描述
给出 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;
}