```
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<set>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
//fileopen();
//P3916
const int maxn = 1e5 + 5;
vector<int> G[maxn], G1[maxn];
int f[maxn];
int n, m;
int bh[maxn];
int cnt,id;
int belong[maxn];
int DFN[maxn], LOW[maxn];
bool insta[maxn];
stack<int> sta;
void solve();
void tarjan(int a);
int dp(int a);
int main() {
scanf( "%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int a, b;
scanf( "%d%d", &a, &b);
G[a].push_back(b);
}
solve();
memset(f, -1, sizeof(f));
for (int i = 1; i <= cnt; i++)
dp(i);
for (int i = 1; i <= n; i++)
printf("%d ", f[belong[i]]);
return 0;
}
void solve() {
id = cnt = 0;
memset(DFN, 0, sizeof(DFN));
memset(insta, false, sizeof(sta));
memset(bh, -1, sizeof(bh));
for (int i = 1; i <= n; i++)
if (!DFN[i])tarjan(i);
for (int a = 1; a <= n; a++) {
for (int i = 0; i < G[a].size(); i++) {
int &b = G[a][i];
if (belong[a] == belong[b])continue;
G1[belong[a]].push_back(belong[b]);
}
}
}
void tarjan(int a) {
LOW[a] = DFN[a] = ++id;
sta.push(a);
insta[a] = true;
for (int i = 0; i < G[a].size(); i++) {
int &b = G[a][i];
if (!DFN[b]) {
tarjan(b);
LOW[a] = min(LOW[a], LOW[b]);
}
else if (insta[b])
LOW[a] = min(LOW[a], LOW[b]);
}
if (DFN[a] == DFN[a]) {
cnt++;
int b;
do {
b = sta.top(); sta.pop();
insta[b] = false;
bh[cnt]=max(bh[cnt],b);
belong[b] = cnt;
} while (a != b);
}
}
int dp(int a) {
int &ans = f[a];
if (ans != -1)return ans;
ans = bh[a];
for (int i = 0; i < G1[a].size(); i++)
ans = max(ans, dp(G1[a][i]));
return ans;
}
```
by zzq233 @ 2018-08-01 13:54:22
~~缩点~~
by zzq233 @ 2018-08-01 14:00:19
这个帖子能删吗
by zzq233 @ 2018-08-01 14:00:33
@[ABC_zzq](/space/show?uid=106799) 过了吗
by walk_alone @ 2018-09-11 20:46:22