题目描述
给出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)。
输入输出样例
输入 #1复制
4 3 1 2 2 4 4 3
输出 #1复制
4 4 3 4
说明/提示
• 对于60% 的数据， 1≤N.M≤ 10^3；
• 对于100% 的数据， 1≤N,M≤10^5 。
#include <iostream> #include <cstdio> #include <vector> using namespace std; #define MAXL 100010 int N, M, A[MAXL]; vector<int> G[MAXL]; //vector存图 void dfs(int x, int d) { if(A[x]) return; //访问过 就是不为0 A[x] = d; for(int i=0; i<G[x].size(); i++) dfs(G[x][i], d); } int main() { int u, v; scanf("%d%d", &N, &M); for(int i=1; i<=M; i++) { scanf("%d%d", &u, &v); G[v].push_back(u); //反向建边 } for(int i=N; i; i--) dfs(i, i); for(int i=1; i<=N; i++) printf("%d ", A[i]); printf("\n"); return 0; }
