40 lines
1.1 KiB
C++
40 lines
1.1 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int N = 100010;
|
||
int n; //n个结点
|
||
int m; //m条边
|
||
int res[N];
|
||
int u, v;
|
||
vector<int> p[N]; //vector存图
|
||
//此代码过了2个测试点，其它MLE，原因：测试数据有环！不加st数组，就死循环了，表现就是MLE!
|
||
/**
|
||
* 深度优先搜索
|
||
* @param x 从哪个号结点出发
|
||
* @param d 已经到达过的最大号结点
|
||
*/
|
||
void dfs(int x, int ne) {
|
||
//没走过，更新最大号为d
|
||
res[x] = max(ne, res[x]);
|
||
//遍历所有出边，尝试找到更大号的结点
|
||
for (int i = 0; i < p[ne].size(); i++) dfs(x, p[ne][i]);
|
||
}
|
||
|
||
int main() {
|
||
//读入
|
||
scanf("%d%d", &n, &m);
|
||
|
||
//构建图
|
||
for (int i = 1; i <= m; i++) {
|
||
scanf("%d%d", &u, &v);
|
||
p[u].push_back(v); //正向建边,结点u出发有一条到结点v的边
|
||
}
|
||
//逐个深度优先搜索,找出每个结点能够到达的最大号结点
|
||
for (int i = 1; i <= n; i++) dfs(i, i);
|
||
|
||
//输出
|
||
for (int i = 1; i <= n; i++) printf("%d ", res[i]);
|
||
printf("\n");
|
||
|
||
return 0;
|
||
} |