tarjan

线性的复杂度求解有向图的强连通分量与无向图的割点割边问题

• 强连通分量
• 割点
• 割边

强连通分量

对于一张无向图，定义一个点的集合中。点两两之间可以相互到达，这个点的元素数量最大化，则称这个点的集合为这个无向图的强连通分量
1.找图中任意一点，从该点开始dfs
2.当点未被遍历时打上时间戳，初始化low[x]=时间戳dfn[x]，将其压入栈中
3.当节点已经被遍历时，说明此时找到了一个强连通分量，用其dfn更新我们当前节点的low
4.当发现搜索完成所有的子树之后，dfn[x]==low[x]，说明当前节点为关键节点，即一个强连通分量的"入口"
5.我们一直弹栈，直到将当前节点弹出，弹出的点都在一个强连通分量中

stack<int > q;
int dfn[N];
int low[N];
int sign[N];
int ans[N];
int num,re;
void tarjan(int x){
	dfn[x]=low[x]=++num;
	q.push(x);
	int k=head[x];
	while(k){
		if(!dfn[e[k].to]){
			tarjan(e[k].to);
			low[x]=min(low[x],low[e[k].to]);
		}else{
			if(!sign[e[k].to]){
				low[x]=min(low[x],dfn[e[k].to]);
			}
		}
		k=e[k].next;
	}
	if(dfn[x]==low[x]){
		sign[x]=++re;
		ans[re]++;
		while(q.top()!=x){
			sign[q.top()]=re;
			ans[re]++;
			q.pop();
		}
		q.pop();
	}
}

为什么需要判遍历到的节点是否已经存在于一个强连通分量中？
假设此节点存在于这个强连通分量中，那么它一定会在退栈之前被搜索到
即现在的情况是，此节点可以便利到强连通分量中的点，但此强连通分量中的点无法到达目前节点
对于强连通分量能否将low[x]=min(low[x],low[e[k].to])改成low[x]=min(low[x],low[e[k].to])?
目前未找到反例，但是dfn[e[k].to]绝对没问题

割点

对于一张无向图，删除某一个点之后，图便不再联通，这个点成为割点
1.任选一个点作为根节点，开始dfs，这个根节点为root
2.当遍历到一个未遍历过的节点，标记时间戳，初始化它的low[x]=dfn[x]
3.当遍历到一个已经访问过的节点，用它的时间戳来更新我们的low[x]
4.我们需要分两种情况讨论一个节点是否属于割点
（1）当前节点为为非根节点
如果其存在一个无法到达其上方的任何一个祖先的子树，那么这个节点时割点
（2）当前节点时根节点
如果根节点不止一个子树，即这个点的任意两棵子树之间必不存在边（如果存在一定会合并成一棵子树）那么这个点是割点

为什么low[x]=min(low[x],dfn[e[k].to])不能改成low[x]=min(low[x],low[e[k].to])?

对于一个割点下的子树而言，出现遍历到已经访问过的节点用其low来更新没有问题，但是存在一个节点用割点的low来更新，那就炸了
即我们对于一个点对其子节点的low的要求是，能通过一条边连接到这个点的祖先，但是不能通过这个点，必须绕过这个点，所以这样是错误的

int ans_coun;
int coun;
bool ans[N];
int root;
int dfn[N];
int low[N];
int num;
void tarjan(int x){
	dfn[x]=low[x]=++num;
	int k=head[x];
	while(k){
		if(!dfn[e[k].to]){
			tarjan(e[k].to);
			low[x]=min(low[x],low[e[k].to]);
			if(x!=root&&low[e[k].to]>=dfn[x]){
				ans[x]=1;
			}
			if(root==x) coun++;
		}else{
			low[x]=min(low[x],dfn[e[k].to]);
		}
		k=e[k].next;
	}
	if(x==root&&coun>1){
		ans[x]=1;
	}
}

割边

当删除图中的一条边时，图不在联通，则这条边称为割边
1.任选一节点开始dfs
2.当一个边未被遍历过时，遍历它，并记录它的时间戳，初始化它的low为dfn
3.当一个点已经被遍历时，用它的dfn 更新我们的low
4.对于当前节点，一条边所连的子树中不存在一条能够回到当前点或者当前点祖先的边，则此边为割边

int ans;
int dfn[N];
int low[N];
int num;
void tarjan(int x){
	dfn[x]=low[x]=++num;
	int k=head[x];
	while(k){
		if(!dfn[e[k].to]){
			tarjan(e[k].to); 
			low[x]=min(low[x],low[e[k].to];)
			if(low[e[k].to]>dfn[x]){
				ans++;
			}
		}else{
			low[x]=min(low[x],dfn[e[k].to]);
		}
		k=e[k].next;
	}
}