图论---tarjan
本篇文章主要是对tarjan不同用法的讲解 ， 其主要目的是复习，当然初学也可以看鸭极有可能看不懂
目录 ：1.有向图缩点
2.无向图割点
3.点双连通分量
1.有向图缩点
首先来一道经典题目
给定一个 n个点 m 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
洛谷3387 缩点
这个题的话很明显我们要用tarjan进行缩点，在图中寻找强连通分量对吧，因为这个点如果我们可以走过去的话，那么他所在的连通分量我们也可以都走一遍在回到这里。
当我们缩晚点之后，剩下的就一定是一个有向无环图（DAG）
证明的话可以用反证法 ， 如果还有环的话就肯定还有连通 ，但这显然不可能
然后我们在这个图上进行一个dp + 拓扑就可以了（这两个不重要）
所以现在我们就来缩点！！！ 先上代码！
#include
using namespace std ;
const int M = 100000 + 5 ;
vector g[M] ;
int bccnum[M] ;
int dfn[M] , low[M] ;
int zhi[M] , z[M] , vis[M] , sum[M] , ru[M];
int ans ;
int gx[6666][6666] , dis[6666];
stack s ;
int cloc = 0 ;
int bccnt = 0 ;
inline void tarjan( int u , int fa)
{
dfn[u] = low[u] = ++cloc ;
s.push(u) ;
for( int i = 0; i > n >> m ;
for( int i = 1 ; i > z[i] ;
}
for( int i = 0 ; i < m ; i++)
{
register int a , b ;
scanf("%d%d" , &a , &b) ;
g[a].push_back(b) ;
}
for( int i = 1 ; i <= n ; i++)
{
if( !dfn[i] )
tarjan(i , i);
}
topu() ;
cout << ans ;
return 0 ;
}
我只留下了与tarjan相关的部分
考虑一个强连通分量C ， 假设第一个被发现的点是x ， 则其他点都是他的后代 ， 这样我们可以在一个DFS中把他们找出来。
现在我们先把这x找出来。对于x的子孙们来说 ， 他们所能到达的祖先点最多就是x，并且不是自己，所以在这个强连通分量（SCC）中只有x自己是low【x】 = dfn【x】的；
所以说当我们找到这个x的时候 ， 我们可以一起把他的子孙们也放到这个SCC
里面 ，这也是我们需要栈的原因；
好了 ， 说这么多只要记住 ：
在有向图中求SCC的时候是low == dfn ， 然后出栈的时候要把这个点也放到这SCC中即可
还有一点 ：else if(!bccnum[nx])low[u] = min( low[u] , dfn[nx]) ;
这句话别忘了前面的条件（可能是我太弱了经常忘qwq）就是说可能你指向的这个点是在你之前被访问过了， 但仅仅只是你单方面想过去人家并不喜欢你
所以是不可以更新的！！！
2.无向图缩点
这个比较简单，上代码， 里面有注释
inline void tarjan( int u , int fa)
{
dfn[u] = low[u] = ++cloc ;
int child = 0 ;
for( int i = head[u] ; i!=0 ; i = pre[i].mark)
{
register int nxx = pre[i].xnt ;
if( !dfn[nxx])
{
tarjan(nxx , fa) ;
low[u] = min( low[u] , low[nxx] ) ;
if( low[nxx] >= dfn[u] && u != fa)//如果说他的孩子们所能到达他的上面，他就不是割点， 不然就是！
cut[u] = 1 ;
if( u == fa)
child++ ;
}
low[u] = min( low[u] , dfn[nxx]) ;
}
if( u == fa && child >= 2)//如果说是根节点，只要有两个以上的孩子就可以割了
cut[u] = 1 ;
}
3.点双连通分量
首先明确点双连通的定义： 任意两点存在点不重复的路径；
所以点双连通分量的极大子图为点双连通分量（BCC）
然后这个是在无向图中废话，但是我们是把边推进栈中 ，因为不同BCC可能有重复的点 ！！！
然后这个看看代码应该可以懂
提供样例：1-2 2-3 1-3 3-4 4-5 5-6 这个图中两个BCC为{1 ， 2 ，3 } 和{3 ， 4, 5} ；
vector bcc[maxn] // 这里用vector存的是一个BCC中有哪些点
//bccnum存的是这个点位于哪一个BCC
//但是不是所有点都可以 ， 比如样例中的3 因为它同时存在于两个BCC中
if(low[v] >= dfn[u]){
bcccnt++ ;
for( ; ; ){
edge x = s.top() ; s.pop() ;
if(bccnum[x.u] != bcccnt){
bcc[bcccnt].push_back(x.u)
bccnum[x.u] = bcccnt ;
}
if(bccnum[x.v] != bcccnt) {
bcc[bcccnt].push_back(x.v)
bccnum[x.v] = bcccnt ;
}
if(x.u == u && x.v == v) break ;
}
}
这个点双连通代码来自lrj的蓝书 请读者自行思考
主要是因为感觉不常用到， 但还是要知道鸭！！！
有向图缩点 ：low[u]==dfn[u]
无向图割点：dfn[u]<=low[v]
点双连通分量：同上 ， 但是入栈的是边
感谢观看，码字不易 ，点个赞吧QWQ
完结撒花
有问题请评论谢谢鸭
作者：洛谷蒟蒻zht
