问题描述
给出一张有向图，可能存在环，对于所有的i，求出从1号点到i点的所有路径上的必经点集合。
什么是支配树
两个简单的小性质——
1.如果i是j的必经点，而j又是k的必经点，则i也是k的必经点。
2.如果i和j都是k的必经点，则i和j之间必然存在必经点关系，不可能互相都不是必经点。
不难发现所有的必经点关系形成了一个以1点为根的树形关系，每个点的支配点集合就是其到根节点（1点）路径上的点集，称这棵树为支配树。
怎么求支配树
假如我们得到的是一个有向无环图，那么只需要$O(N)$的做一遍拓扑排序就可以了，非常简单。
假如我们得到了一张有向有环图，那么我们可以$O(N)$的枚举一个点，把它从图上删去，从根$O(M)$的DFS（或BFS）一次，就可以知道它是哪些点的必经点，复杂度$O(NM)$，简单粗暴，但时间复杂度难以接受。
然后就有了Lengauer-Tarjan算法，复杂度为$O(NlogN)$，有一堆定理证明，想详细的搞明白最好去看Tarjan的英文论文，网上有些中文翻译难免带些小错误。
简单的上手题
据某位大佬说，这个算法还没见到过不是裸题的题…… OTZ
不过确实，目前这个算法一般应用在浅层，题面也是非常的裸，简直就是再说“快来拿支配树上我啊！”
CodeChef Counting on a directed graph GRAPHCNT
#include <bits/stdc++.h> using namespace std; typedef long long lnt; const int mxn = ; int n, m; int tim;
int dfn[mxn];
int idx[mxn];
int fat[mxn];
int idm[mxn];
int sdm[mxn];
int anc[mxn];
int tag[mxn];
lnt siz[mxn];
lnt son[mxn]; vector<int> G[mxn];
vector<int> R[mxn];
vector<int> S[mxn];
vector<int> T[mxn]; void dfsG(int u)
{
idx[dfn[u] = ++tim] = u; for (auto v : G[u])if (!dfn[v])
fat[v] = u, dfsG(v);
} void dfsT(int u)
{
siz[u] = ; for (auto v : T[u])
dfsT(v), siz[u] += siz[v];
} int find(int u)
{
if (u == anc[u])
return u; int r = find(anc[u]); if (dfn[sdm[tag[anc[u]]]] < dfn[sdm[tag[u]]])
tag[u] = tag[anc[u]]; return anc[u] = r;
} signed main(void)
{
cin >> n >> m; for (int i = , u, v; i <= m; ++i)
{
cin >> u >> v;
G[u].push_back(v);
R[v].push_back(u);
} for (int i = ; i <= n; ++i)
sdm[i] = tag[i] = anc[i] = i; dfsG(); for (int i = tim; i > ; --i)
{
int u = idx[i]; for (auto v : R[u])if (dfn[v])
{
find(v);
if (dfn[sdm[tag[v]]] < dfn[sdm[u]])
sdm[u] = sdm[tag[v]];
} anc[u] = fat[u]; S[sdm[u]].push_back(u); int t = idx[i - ]; for (auto v : S[t])
{
find(v);
if (sdm[tag[v]] == t)
idm[v] = t;
else
idm[v] = tag[v];
} S[t].clear();
} for (int i = ; i <= tim; ++i)
{
int u = idx[i];
if (idm[u] != sdm[u])
idm[u] = idm[idm[u]];
} for (int i = ; i <= tim; ++i)
T[idm[i]].push_back(i); dfsT(); lnt ans = tim * (tim - ); for (int i = tim, u; i >= ; --i)
{
++son[u = idx[i]];
if (idm[u] != )
son[idm[u]] += son[u];
else
ans -= son[u] * (son[u] - );
} ans >>= ; cout << ans << endl;
}
#include <cstdio>
#include <cstring> #define mxn 50005
#define mxm 200005
#define lnt long long int n, m; struct Lin {
int tt;
int hd[mxn];
int nt[mxm];
int to[mxm]; void init(void) {
memset(hd, , sizeof hd), tt = ;
} void adde(int u, int v) {
nt[++tt] = hd[u], to[tt] = v, hd[u] = tt;
}
}G, R, T, S; int tim;
int idx[mxn];
int dfn[mxn];
int fat[mxn];
int anc[mxn];
int tag[mxn];
int sdm[mxn];
int idm[mxn];
lnt ans[mxn]; void dfsG(int u) {
idx[dfn[u] = ++tim] = u; for (int i = G.hd[u], v; i; i = G.nt[i])
if (!dfn[v = G.to[i]])dfsG(v), fat[v] = u;
} void dfsT(int u) {
ans[u] += u; for (int i = T.hd[u], v; i; i = T.nt[i])
ans[v = T.to[i]] += ans[u], dfsT(v);
} int find(int u) {
if (anc[u] == u)return u; int r = find(anc[u]); if (dfn[sdm[tag[anc[u]]]] < dfn[sdm[tag[u]]])
tag[u] = tag[anc[u]]; return anc[u] = r;
} signed main(void)
{
while (scanf("%d%d", &n, &m) != EOF) {
memset(ans, , sizeof ans);
memset(dfn, , sizeof dfn), tim = ; G.init(); R.init(); T.init(); S.init(); for (int i = , u, v; i <= m; ++i)
scanf("%d%d", &u, &v), G.adde(u, v), R.adde(v, u); for (int i = ; i <= n; ++i)
sdm[i] = tag[i] = anc[i] = i; dfsG(n); for (int i = tim; i > ; --i) {
int u = idx[i], v; for (int j = R.hd[u]; j; j = R.nt[j])
if (dfn[v = R.to[j]]) {
find(v);
if (dfn[sdm[tag[v]]] < dfn[sdm[u]])
sdm[u] = sdm[tag[v]];
} anc[u] = fat[u]; S.adde(sdm[u], u); u = idx[i - ]; for (int j = S.hd[u]; j; j = S.nt[j]) {
find(v = S.to[j]);
if (sdm[tag[v]] == u)
idm[v] = u;
else
idm[v] = tag[v];
}
} for (int i = ; i <= tim; ++i) {
int u = idx[i];
if (idm[u] != sdm[u])
idm[u] = idm[idm[u]];
T.adde(idm[u], u);
} dfsT(n); for (int i = ; i < n; ++i)
printf("%lld ", ans[i]); printf("%lld\n", ans[n]);
}
}
SPOJ BIA - Bytelandian Information Agency
#include <bits/stdc++.h> using namespace std; const int mxn = ;
const int mxm = ; int n, m; vector<int> G[mxn];
vector<int> R[mxn];
vector<int> S[mxn]; inline void init(vector<int> v[mxn])
{
for (int i = ; i < mxn; ++i)
v[i].clear();
} int tim;
int dfn[mxn];
int idx[mxn];
int fat[mxn];
int idm[mxn];
int sdm[mxn];
int anc[mxn];
int cnt[mxn];
int tag[mxn]; void dfsG(int u)
{
idx[dfn[u] = ++tim] = u; for (auto v : G[u])if (!dfn[v])
fat[v] = u, dfsG(v);
} int find(int u)
{
if (anc[u] == u)
return u; int r = find(anc[u]); if (dfn[sdm[tag[anc[u]]]] < dfn[sdm[tag[u]]])
tag[u] = tag[anc[u]]; return anc[u] = r;
} signed main(void)
{
while (cin >> n >> m)
{
init(G);
init(R);
init(S); tim = ; memset(cnt, , sizeof cnt);
memset(dfn, , sizeof dfn); for (int i = , u, v; i <= m; ++i)
{
cin >> u >> v;
G[u].push_back(v);
R[v].push_back(u);
} for (int i = ; i <= n; ++i)
sdm[i] = tag[i] = anc[i] = i; dfsG(); for (int i = tim; i > ; --i)
{
int u = idx[i]; for (auto v : R[u])if (dfn[v])
{
find(v);
if (dfn[sdm[tag[v]]] < dfn[sdm[u]])
sdm[u] = sdm[tag[v]];
} anc[u] = fat[u]; S[sdm[u]].push_back(u); u = idx[i - ]; for (auto v : S[u])
{
find(v); if (sdm[tag[v]] == u)
idm[v] = u;
else
idm[v] = tag[v];
} S[u].clear();
} for (int i = ; i <= tim; ++i)
{
int u = idx[i];
if (idm[u] != sdm[u])
idm[u] = idm[idm[u]];
} for (int i = ; i <= tim; ++i)
++cnt[idm[i]]; int ans = ; for (int i = ; i <= tim; ++i)
if (cnt[i])++ans; cout << ans << endl; for (int i = ; i <= tim; ++i)
if (cnt[i])cout << i << " "; cout << endl;
}
}
@Author: YouSiki