【模板】Tarjan

\(\color{black}{Tarjan}\)是在\(dfs\)的过程中维护了一个栈，以及\(low\)(回溯值)，\(dfn\)（时间戳）两个数组。

\(low\)和\(dfn\)的计算

\(dfn\)就在\(dfs\)的过程中打就可以了，而\(low\)的计算方式稍稍复杂一些：

1.如果\(x-y\)为树枝边（\(y\)未被访问），则\(low_x = \min(low_x,low_y)\)

2.如果\(x-y\)为返祖边（\(y\)在栈中），则\(low_x = \min(low_x,dfn_y)\)

3.除此之外，啥都不干

强连通分量

在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通。

如果有向图G的每两个顶点都强连通，称G是一个强连通图。

非强连通图有向图的极大强连通子图，称为强连通分量。

则通过手模易得：\(\text{当一个点}x\text{经过}dfs\text{后},dfn_x =low_x,\text{则栈中}x\text{以上的点构成一个强连通分量}\)

bool instk[z];
int ti, dfn[z], low[z], belong[z];
stack stk;
void tarjan(int u) {
	dfn[u] = low[u] = ++ti;
	stk.push(u);
	instk[u] = true;
	for(int i = head[u];i;i = edge[i].next) {
		if(!dfn[edge[i].t]) {
			tarjan(edge[i].t);
			low[u] = min(low[u],low[edge[i].t]);
		} else if(instk[edge[i].t]) {
			low[u] = min(low[u],dfn[edge[i].t]);
		}
	}
	if(low[u] == dfn[u]) {
		int tmp;
		++belong[0];
		do {
			tmp = stk.top();
			stk.pop();
			instk[tmp] = false;
			belong[tmp] = belong[0];
		} while(tmp != u);
	}
}

割点

若删掉某点后，原连通图分裂为多个子图，则称该点为割点。

则易得：\(\text{若一点}x\text{的}low_x \ge dfn_x,\text{则}x\text{为割点}\)

bool cutPoint[z];
int ti, root, dfn[z], low[z];
void tarjan(int u) {
	dfn[u] = low[u] = ++ti;
	int son = 0;
	for(int i = head[u];i;i = edge[i].next) {
		if(!dfn[edge[i].t]) {
			++son;
			tarjan(edge[i].t);
			low[u] = min(low[u],low[edge[i].t]);
			if(dfn[u] <= low[edge[i].t]) 
				if(u != root||son > 1) cutPoint[u] = true;
				//注意如果u为起点,至少有两棵子树才算割点;
		} else if(instk[edge[i].t]) {
			low[u] = min(low[u],dfn[edge[i].t]);
		}
	}
}

割边（桥）

删掉某边之后，图会分裂为两个或两个以上的子图，则该边为桥。

则易得：\(\text{若某边}x-y\text{有}low_x > dfn_y,\text{则该边为割边}\)

进一步，则有

1.\(low_x = dfn_x\)

2.\(dfn_x < low_y\)

3.\(\text{前两种综合，}\)

bool cutEdge[z];
int ti, dfn[z], low[z], cut, pEdge[z];
void tarjan(int u) {
	dfn[u] = low[u] = ++ti;
	for(int i = head[u];i;i = edge[i].next) {
		if(i == (pEdge[u]^1)) continue;
		if(!dfn[edge[i].t]) {
			pEdge[edge[i].t] = i;
			tarjan(edge[i].t);
			low[u] = min(low[u],low[edge[i].t]);
			if(dfn[u] > low[edge[i].t]) {
				cut++;
				cutEdge[i] = cutEdge[i^1] = true;
			}
		} else {
			low[u] = min(low[u],dfn[edge[i].t]);
		}
	}
}

点、边双连通分量

若一个无向图中的去掉任意一个节点（一条边）都不会改变此图的连通性，即不存在割点（桥），则称作点（边）双连通图。

一个无向图中的每一个极大点（边）双连通子图称作此无向图的点（边）双连通分量。求双连通分量可用\(Tarjan\)算法。

1.点双联通分量

对于点双连通分支，实际上在求割点的过程中就能顺便把每个点双连通分支求出。建立一个栈，存储当前双连通分支，访问每个点时把这个点入栈。

如果某时满足\(dfn_u\le low_v\)，说明u是一个割点，那么把点从栈顶一个个取出，直到遇到了点\(u\)（\(u\)不取出），取出的这些点和\(u\)组成一个点双连通分支。

割点可以属于多个点双连通分支，其余点和每条边只属于且属于一个点双连通分支。

bool cutPoint[z];
int ti, dfn[z], low[z], cut, root;
stack stk;
vector pbcc[z], belong[z];
void tarjan(int u,int p) {
	dfn[u] = low[u] = ++ti;
	stk.push(u);
	bool first = true;
	int sub = 0;
	for(int i = head[u];i;i = edge[i].next) {
		if(first&&edge[i].t == p) {
			first = false;
			continue;
		}
		if(!dfn[edge[i].t]) {
			++sub;
			tarjan(edge[i].t,u);
			low[u] = min(low[u],low[edge[i].t]);
			if(dfn[u] <= low[edge[i].t]) {
				cutPoint[u] = true;
				cut++;
				pbcc[cut].push_back(u);
				int tmp;
				do {
					tmp = stk.top();
					stk.pop();
					pbcc[cut].push_back(tmp);
					belong[tmp].push_back(cut);
				} while(tmp != edge[i].t);
			}
		} else {
			low[u] = min(low[u],dfn[edge[i].t]);
		}
	}
	if(u == root&&sub == 1) 
		cutPoint[u] = false;
}

2.边双连通分量

对于边双连通分支，求法更为简单。只需在求出所有的桥以后，把桥边删除，原图变成了多个连通块，则每个连通块就是一个边双连通分支。

桥不属于任何一个边双连通分支，其余的边和每个顶点都属于且只属于一个边双连通分支。

stack stk;//栈；
vector ebc[z];//存每一个边双联通分量；
bool cut[z];//边是否为桥；
int dfn[z], low[z], ti;
int belong[z];//判断某点在哪一个分量里；
void tarjan(int &u,int &pid) {
    dfn[u] = low[u] = ++ti;
    stk.push(u);
    for(int i = head[u];i;i = edge[i].next) {
        if(i == (pid^1)) continue;//WARNING！加括号！
        if(!dfn[edge[i].t]) {
            tarjan(edge[i].t,i);//顺便这里判的一直是边的id；
            low[u] = min(low[u],low[edge[i].t]);
        } else {
            low[u] = min(low[u],dfn[edge[i].t]);
        }
    }
    if(dfn[u] == low[u]) {//发现有桥，开始找分量；
        cut[pid] = true;
        ++belong[0];
        int tmp;
        do {
            tmp = stk.top();
            stk.pop();
            belong[tmp] = belong[0];
            ebc[belong[0]].push_back(tmp);
        } while(tmp != u);
    }
    return;
}

3.构造边双连通分量

若一个有桥的连通图的叶子结点数量为\(n\)，则至少要加\(\left\lfloor\dfrac{n+1}{2}\right\rfloor\)条边就能使该图变为边双连通图。

具体方法为，首先在两个最近公共祖先最远的两个叶节点之间连接一条边，把这两个点到祖先的路径上所有点收缩到一起，再继续祖先最远的两个叶节点，以此类推。

LCA（施工中）

我们先读入所有的询问并对这些询问构建一个邻接表。

在遍历到u时，先tarjan遍历完u的子树，则u和u的子树中的节点的最近公共祖先就是u，并且u和u的兄弟节点及其子树的最近公共祖先就是u的父亲。

用一个color数组，正在访问的节点标记为1，未访问的标记为0，已经访问到的即在u的子树中的及u的已访问的兄弟节点及其子树中的标记为2。

再维护一个并查集，访问完节点u的一个子树时，就把这个子树的根节点的fa改为u。访问完u的所有子树后，考虑所有与u相关的询问lca(u,v)，那么lca(u,v)就是v所在并查集的根。

这是一个离线算法，时间复杂度为O(Nα(N))，约为O(N)。

int p[z], color[z];
void tarjan(int u) {
	p[u] = u;
	color[u] = 1;
	int y;
	for(int i = head[u];i;i = edge[i].next) {
		if(color[y = ver[i]] == 0) {
			tarjan(y);
			p[y] = x;
		}
	}
	for(int i = headquery[u];i;i = query[i].next) {
		if(color[y = query[i]] == 2) ans[i] = get(y);
	}
	color[u] = 2;
}