RT

30pts

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int maxm = 1e5 + 5;

int n, m;

int tot, to[maxn], head[maxm * 2], nxt[maxm * 2];
void add(int u, int v) {
	tot++;
	to[tot] = v;nxt[tot] = head[u];head[u] = tot;
}
struct Edge {
	int from, to; 
}e[maxm]; 

stack<int> s;//栈 
int dfn[maxn], co[maxn], col, num, low[maxn];
int tj[maxn],ans[maxn];
/*
dfn[u] u节点的时间戳   num是当前的“时间”
co[u]  u节点分别属于哪个强连通分量  col是对应的编号
low[u] u节点的或u的子树能够回溯到的最早的栈中的节点的dfn值 
*/
void tarjan(int u) {
	dfn[u] = low[u] = ++num;  // 初始化该点的时间戳以及它最早能够回溯到的点至少是它自己
	s.push(u); // 将u节点加入栈中
	for(int i = head[u];i;i = nxt[i]) {
		int v = to[i];
		if(!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]); // 对于u点来说，它能够到达的最早的节点可能是由它或它的子节点到达的 
		}
		else if(!co[v])low[u] = min(low[u], dfn[v]); 	// 如果v节点不属于任何一个强连通分量,那么就判断v本身是否在low[u]前面 
	}
	
	// 标记强连通分量 
	if(low[u] == dfn[u]) {  // 当这个点能够回溯到最早的点等于它的时间戳时，说明它属于一个新的强连通分量 
		co[u] = ++col; // 标记上一个强连通分量 
		tj[col]=u;
		while(s.top() != u) {  //  将栈内所有节点都打上标记 
			co[s.top()] = col;
			tj[col]=max(tj[col],s.top());
			s.pop();
		} 
		s.pop(); // 将自己弹出 
	} 
} 

void rebuild() {
	tot = 0;
	memset(head, 0, sizeof(head) );
	for(int i = 1;i <= m;i++) {
		int u = e[i].from, v = e[i].to;
		if(co[v] == co[u])return;
		add(co[u], co[v]);
	}
}

void dfs(int u) {
	ans[u] = tj[u];
	for(int i = head[u];i;i = nxt[i]) {
		int v = to[i];
		dfs(v);
		ans[u] = max(ans[u], ans[v]);
	}
}

int main() {
	cin >> n >> m;
	for(int i = 1;i <= m;i++) {
		register int u, v;
		cin >> u >> v;
		e[i].from = u, e[i].to = v;
		add(u, v);
	}
	for(int i = 1;i <= n;i++)if(!dfn[i])tarjan(i); //利用tarjan缩点 
	rebuild();
	for(int i = 1;i <= col;i++) {
		if(!ans[i])dfs(i);
	}
	for(int i = 1;i <= n;i++)cout << ans[co[i]] << " ";
	return 0; 
}