这是有关有向图连通性的妇孺皆知我不知的一些东西
• Flow Graph: 若有向图$G$中存在一点$r$，从$r$出发可以到达$G$中所有的点，则称$G$是FlowGraph，记为$(G,r)$
• 搜索树(Dfs Tree): 从$r$出发对$G$进行深度优先遍历，递归时经过的有向边构成一棵树，称为$G$以$r$为根的搜索树
• 时间戳(Dfn): dfn表示时间戳，id表示时间戳对应的节点
Flow Graph$(G,r)$里面边的类型:
• 树枝边(tree arcs)：边$(x,y)$在搜索树$T$中；
• 前向边(forward arcs)：在$T$中存在一条从$x$到$y$的路径；
• 后向边(cycle arcs)：在$T$中存在一条从$y$到$x$的路径；
• 横叉边(cross arcs)：在$T$中既没有$x$到$y$的路径，也没有$y$到$x$的路径，并且dfn[y]<dfn[x]。
$(G,r)$也就只有这点边了
然后是关于割点的定义:
• 必经点(即有向图割点): 若在$(G,r)$中从$r$到$y$的路径一定经过点$x$，则称$x$是从$r$到达$y$的必经点，记为$x\ dom\ y$
• 必经点集合: 从$r$出发到达$y$的所有必经点构成的集合记为$dom(y)$，即$dom(y)=\lbrace x \mid x ~dom ~y \rbrace$
• 最近必经点(idom): 节点$y$的必经点集合$dom(y)$中dfn值最大的点$x$是距离$y$最近的必经点，称为$y$的最近必经点。最近必经点是唯一的，因此可以记$x=idom(y)$
然后是奇怪的半必经点:
• 半必经点(semi): 在搜索树$T$上点$y$的祖先中，通过非树枝边可以到达$y$的深度最小的祖先$x$，称为$y$的半必经点。半必经点也是唯一的，因此可以记$x=semi(y)$
* 这里有个坑就是一个点的父亲也可以是它的$semi$
• 半必经点定理:
对于$G$中的一点$y$，考虑所有$x \in pre(y)$[即$\exists(x,y)$]，定义一个临时变量$temp=+\infty$
若$dfn[x]<dfn[y]$，则$(x,y)$为树枝边或前向边，此时$temp=\min(temp,dfn[x])$
若$dfn[x]>dfn[y]$，则$(x,y)$为横叉边或后向边，此时$\forall x$在$T$中的祖先$z$，满足$dfn[z]>dfn[y]$时，有$temp=min(temp,dfn[semi[z]])$
$semi[y]=id[temp]$。即在上述所有可能情况中取$dfn$值最小的一种，就是$y$的半必经点。
注意半必经点不一定是必经点
由于论文没有证明，我来简要证明一下
* if $dfn[x]<dfn[y]$ 如果这条边是横叉边，那么由深搜的性质，$y$点会被先搜到，而不是分在两个子树里，所以这条边只可以是前向边或树枝边，$semi[y]=\min(semi[y],dfn[x])$显而易见
* if $dfn[x]>dfn[y]$ 上定理成立的原因:$semi[y]=dfn[semi[z]]$是显然的，相当于从自己的一个祖先跳到别的树枝上再跳回来。然后又要满足$semi[y]$的最小性，所以取$\min$。
* Q&A:
Q:如果没有自己祖先跳到别的树枝上再跳回来的边呢?[即$\min(dfn[semi[z]])>dfn[y]$]
A:那么这个还有$dfn[x]<dfn[y]$的情况，至少父亲会用一条树枝边指向它，由定理中的*那条，父亲可以是他的$semi$，所以不影响
那么这个定理就证明完了
还有一个必经点定理:
• 对于$G$中的一点$x$，考虑搜索树$T$中semi(x)到$x$的路径上除端点之外的点构成的集合$path$
• 设$y=id[\min\lbrace dfn[semi(z)] \mid z\in path\rbrace ]$，即path中半必经节点的时间戳最小的节点。
• $idom(x)=\begin{cases}semi(x), &\text{semi(x) = semi(y)} \\ idom(y), & \text{semi(x) $\neq$ semi(y)} \end{cases}$
证明:
* Q&A:
Q: 为什么不包含端点
A: 首先显然是不包含$x$自己的，然后如果包含了semi(x),那么它的idom岂不会沿着semi(x)一直跳，那还搞…*&
Q: 为什么要找$y=id[\min\lbrace dfn[semi(z)] \mid z\in path\rbrace ]$?
A: 因为首先$path$是$(semi[x] \to x)$的路径，$semi[x]$有到$x$的边。也就是说，$idom[x] \leq semi[x]$ ，最小的$semi[y]$,有一条跳向$y$的边，$y$有一条通往$x$的树枝边，又$y$到$x$之间不存在$idom[x]$$(idom[x]\leq semi[x])$，说明必经点必定在$semi[y]$之前，或者说，必经点就是$idom[y]$
Q: 那不是有可能点$z$的$idom[z]<idom[y]$呀，答案不应该是$\min\lbrace idom[z] \mid z \in path\rbrace $么($idom[z]$指其dfs序)
A: 这个很有道理，但是这样的话$idom[y]$也就$~=idom[z]$了
那么证明算是结束了
有了这些乱七八糟的玩意我们就可以构建一棵Dominator Tree
• 设有向图$G=(V,E)$，$(G,r)$是一个Flow Graph，则称$(G,r)$的子图$D=(V,\lbrace (idom(i),i) \mid i \in V,i \neq r \rbrace,r)$为$(G,r)$的一棵Dominator Tree。
• $(G,r)$的DominatorTree是一棵有向有根树，从$r$出发可以到达$G$中的所有点，并且树上的每条边$(u,v)$都满足：$u=idom(v)$，即父节点是子节点的最近必经点。
• $x=idom(y)$，当且仅当有向边$(x,y)$是DominatorTree中的一条树枝边。
• $x\ dom\ y$，当且仅当在DominatorTree中存在一条从$x$到$y$的路径。
• $x$的必经点集合$dom(x)$就是DominatorTree上x的所有祖先以及$x$自身。
看看看，性质多么优良的一棵树！自适应有向图的连通性问题呢！
接下来讲构建,用到Lengauer-Tarjan算法:
• Lengauer和Tarjan于1979年提出，经典Tarjan算法的进一步应用。
• 时间复杂度$O(NlogN)$或$O(Nα(N))$，几乎接近于线性。
• 基本思想：
• 通过DFS构建搜索树，并计算出每个节点的时间戳。
• 根据半必经点定理，按照时间戳从大到小的顺序计算每个节点的半必经节点。
• 根据必经点定理，按照时间戳从小到大的顺序，把半必经节点≠必经节点的节点进行修正。
这个最好自己理解下，用到了之前的定理以及dfs序的性质，附代码:
int dfn[M],tid[M],anc[M],dfs_clock;
int idom[M],semi[M],best[M],f[M];
//anc:并查集的集合标号 best:就是那个路径压缩维护的东西
typedef vector<int> vec;
vec pre[M],G[M],dom[M];
//pre[x]:x的前驱节点 G[x]:x的后向节点 dom:新图
inline void predfs(int v){
dfn[v]=++dfs_clock,tid[dfs_clock]=v;
semi[dfs_clock]=anc[dfs_clock]=best[dfs_clock]=dfs_clock;
for(int i=0;i<G[v].size();++i){
int to=G[v][i];
if(!dfn[to])predfs(to),f[dfn[to]]=dfn[v];
}
}
inline int get(int x){
if(anc[x]==x)return x;
int y=get(anc[x]);
if(semi[best[x]]>semi[best[anc[x]]])best[x]=best[anc[x]];
//maintain
anc[x]=y;//path compression
return y;
}
inline void Min(int &a,int b){
if(a>b)a=b;
}
inline void Tarjan(){
//注意新图完全构建在dfs序上
#define pb push_back
for(int i=1,a,b;i<=m;++i){
scanf("%d %d",&a,&b);
G[a].pb(b),pre[b].pb(a);
}
predfs(1);
for(int y=dfs_clock;y>1;--y){
int x=f[y],w=tid[y];
for(int i=0;i<pre[w].size();++i){
int z=dfn[pre[w][i]];
if(!z)continue;
get(z);
Min(semi[y],semi[best[z]]);
}
dom[semi[y]].pb(y);
anc[y]=x;
for(int i=0,z;i<dom[x].size();++i){
z=dom[x][i];
get(z);
if(semi[best[z]]<x)idom[z]=best[z];
else idom[z]=x;
}
dom[x].clear();
}
for(int i=2;i<=dfs_clock;++i){
if(idom[i]!=semi[i])idom[i]=idom[idom[i]];
dom[idom[i]].pb(i);
}
}
直接就有题解了自己点上面的标题
有一棵$n$个节点以$n$为源的树。问每个节点到$n$节点的必经点的编号和。
目测不需要
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define bug(x) cout<<#x<<"="<<x<<" "
#define debug(x) cout<<#x<<"="<<x<<endl
const int M=5e4+5;
typedef long long ll;
int n,m;
inline void rd(int &a){
a=0;char c;
while(c=getchar(),!isdigit(c));
do a=a*10+(c^48);
while(c=getchar(),isdigit(c));
}
struct Edge{
int to,nxt;
}G[M<<1][3];
int head[M][3],tot_edge[3];
inline void add_edge(int from,int to,int f){
G[tot_edge[f]][f]=(Edge){to,head[from][f]};
head[from][f]=tot_edge[f]++;
}
inline void Min(int &a,int b){
if(a>b)a=b;
}
int best[M],anc[M],semi[M],idom[M];
int dfn[M],f[M],tid[M],dfs_clock;
inline void predfs(int v){
dfn[v]=++dfs_clock;
tid[dfs_clock]=v;
for(int i=head[v][0];~i;i=G[i][0].nxt){
int to=G[i][0].to;
if(dfn[to])continue;
predfs(to),f[dfn[to]]=dfn[v];
}
}
inline int get(int x){
if(x==anc[x])return x;
int y=get(anc[x]);
if(semi[best[x]]>semi[best[anc[x]]])best[x]=best[anc[x]];
return anc[x]=y;
}
ll res[M];
template<class T>void nt(T x){
if(!x)return;
nt(x/10);
putchar(48+x%10);
}
template<class T>void pt(T x){
if(!x)putchar('0');
else nt(x);
}
inline void dfs(int v){
res[tid[v]]+=tid[v];
for(int i=head[v][2];~i;i=G[i][2].nxt){
int to=G[i][2].to;
res[tid[to]]+=res[tid[v]];
dfs(to);
}
}
inline void Init(){
for(int i=1;i<=n;++i){
best[i]=anc[i]=semi[i]=i;
idom[i]=res[i]=dfn[i]=0;
for(int j=0;j<3;++j)
head[i][j]=-1;
}
dfs_clock=f[1]=0;
memset(tot_edge,0,sizeof tot_edge);
}
inline void gao(){
Init();
for(int i=1,a,b;i<=m;++i){
rd(a),rd(b);
add_edge(a,b,0),add_edge(b,a,1);
}
predfs(n);
for(int y=dfs_clock;y>1;--y){
int x=f[y];
for(int i=head[tid[y]][1];~i;i=G[i][1].nxt){
int z=dfn[G[i][1].to];
if(!z)continue;
get(z);
Min(semi[y],semi[best[z]]);
}
anc[y]=x;
add_edge(semi[y],y,2);
for(int i=head[x][2];~i;i=G[i][2].nxt){
int z=G[i][2].to;
get(z);
if(semi[best[z]]<x)idom[z]=best[z];
else idom[z]=x;
}
head[x][2]=-1;
}
for(int x=2;x<=dfs_clock;++x){
if(idom[x]!=semi[x])idom[x]=idom[idom[x]];
add_edge(idom[x],x,2);
}
dfs(1);
for(int i=1;i<n;++i)
pt(res[i]),putchar(' ');
pt(res[n]),putchar('\n');
}
int main(){
for(;cin>>n>>m;)gao();
return 0;
}