1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
| #include <bits/stdc++.h>
#define int long long
using namespace std;
const int Maxn = 50000 + 10, Maxm = 100000 + 10;
int N, M;
int e, Begin[Maxn], To[Maxm * 2], Next[Maxm * 2];
int Index, dfn[Maxn], id[Maxn], fa[Maxn], f[Maxn], val[Maxn], idom[Maxn], semi[Maxn];
int Ans[Maxn];
vector <int> dom[Maxn], vec[Maxn];
inline void Init()
{
e = Index = 0;
for (int i = 1; i <= N; ++i) vec[i].clear(), dom[i].clear(), Begin[i] = dfn[i] = idom[i] = Ans[i] = 0, f[i] = val[i] = semi[i] = i;
}
inline void add_edge (int x, int y)
{
To[++e] = y;
Next[e] = Begin[x];
Begin[x] = e;
}
inline void dfs (int x)
{
dfn[x] = ++Index;
id[Index] = x;
for (int i = Begin[x]; i; i = Next[i])
{
int y = To[i];
vec[y].push_back(x);
if (dfn[y]) continue;
fa[y] = x;
dfs(y);
}
}
inline int find (int x)
{
if (f[x] == x) return x;
int y = find(f[x]);
if (dfn[semi[val[f[x]]]] < dfn[semi[val[x]]]) val[x] = val[f[x]];
return f[x] = y;
}
inline void Calc ()
{
for (int i = 1; i <= Index; ++i)
{
int x = id[i];
Ans[x] += x;
if (idom[x]) Ans[x] += Ans[idom[x]];
}
}
inline int mmin (int x, int y)
{
return dfn[x] < dfn[y] ? x : y;
}
main()
{
#ifdef hk_cnyali
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif
while (~scanf("%lld%lld", &N, &M))
{
Init();
for (int i = 1; i <= M; ++i)
{
int x, y;
scanf("%lld%lld", &x, &y);
add_edge (x, y);
}
dfs(N);
for (int i = Index; i > 1; --i)
{
int x = id[i];
for (int j = 0; j < vec[x].size(); ++j)
{
int now = vec[x][j];
if (dfn[now] < dfn[x]) semi[x] = mmin(semi[x], now);
else
{
find(now);
semi[x] = mmin(semi[x], semi[val[now]]);
}
}
f[x] = fa[x], dom[semi[x]].push_back(x);
for (int j = 0; j < dom[fa[x]].size(); ++j)
{
int now = dom[fa[x]][j]; find(now);
idom[now] = (dfn[semi[val[now]]] < dfn[semi[now]]) ? val[now] : fa[x];
}
}
for (int i = 2; i <= Index; ++i)
{
int x = id[i];
if (idom[x] != semi[x]) idom[x] = idom[idom[x]];
}
Calc();
cout<<Ans[1];
for (int i = 2; i <= N; ++i)
cout<<" "<<Ans[i];
cout<<endl;
}
return 0;
}
|