网站建设专题/学做网站需要学什么
$$Tarjan$$
求连通分量
先言
别问我为什么不会\(Tarjan\)(这里指的是求强连通分量)，我也不知道，反正我就是不会\(Tarjan\),但是在\(TZT\)学长和\(Luckyblock\)(好像没他啥事)和紫书的帮助下,我搞出来了，并做了几道题，感觉良好
工作流程
怎么来的那种套话就不说了，反正知道是一个叫\(Tarjan\)的老爷爷发明的就行，见得多了。
明确一下一些约定
\(1.\)强联通分量，是两个点相互到达叫做强联通，一个图\(G\)中一个子图\(G'\)，其中\(G'\)中任意两个相互到达，那么子图\(G'\)叫做\(G\)的一个强联通分量，其中，我们认定，一个点，也认为它是强联通分量
\(2.\)缩点 ： 基于环的一个操作，当然，准确的来说，应该基于一个强联通分量的的操作，因为一个点也算，那么如果这个图本身就是个\(DAG\),那也是可以缩点的，但是，没啥
用,不，用处可大了，增加无用的空间，时间复杂度，以及一系列的常数。
![]()
我们规定一些东西：
\(dfn_i\)表示搜索树上的时间戳，也就是第几个遍历到的。
\(low_i\)表示以节点\(i\)为根的子树中节点和可以通过一条不是搜索树上的边可以到达的点的最小值，其中这个节点\(i\)是必然存在的。
> > 证明 你不会以为真是我证明的吧，来源于oi-wiki
>
> 反证法：假设有个结点 \(v\)在该强连通分量中但是不在以\(u\)为根的子树中，那么 \(u\)到\(v\) 的路径中肯定有一条离开子树的边。但是这样的边只可能是横叉边或者反祖边，然而这两条边都要求指向的结点已经被访问过了，这就和 是第一个访问的结点矛盾了。得证。
上面的证明如果不知道横叉边或者返祖边，请点击\(link\),笔者由于看过这篇文章，必然是明白的
我们先来代码(我就是看代码看会的)：
void tarjan(int u )
{
low[u] = dfn[u] = ++ sum ;
stack[++top] = u ;
for(int i = h[u] ; i ; i = e[i].nxt)
{
int v = e[i].v ;
if(!dfn[v])
{
tarjan(v) ;
low[u] = min (low[u] , low[v]) ;
}
else if(!in[v]) low[u] = min (low[u] , dfn[v]) ;
}
if(low[u] == dfn[u])
{
in[u] = ++ cnt ;
++scc[cnt] ;
while(stack[top + 1] != u )
{
++scc[cnt] ;
in[stack[top]] = cnt ;
top -- ;
}
}
}
其中说一下其中变量的意思，我猜应该是看不懂的。
\(low,dfn\)不必多说了，\(h,e\)表示的是链式前向星存图，相信应该都是没有问题的。
\(in_x\)表示的\(x\)这一个节点隶属于哪一个连通块(也就是强连通分量)
\(stack\)表示还没有划分成连通块的节点
\(scc\)表示的联通块的大小
\(cnt\)就表示总共有多少个联通块
\(top\)显然就是栈顶
然后结合一下图来说明：
![]()
很显然，通过上帝视角，我们发现，其中的强连通分量是(我们用集合来表示一下)
\((1 \to 2 \to5) , (4\to 6 \to 7) , 3\)这三个连通分量， 同样的，我们来手动模拟一下\(Tarjan\)算法的这个过程
首先，我们是进行了\(DFS\)，搜索(为了简述方便，我们规定这一个搜索的顺序是从左到右的) ，就可以得到这么一个手动模拟的过程
![]()
之后我们发现，再次从\(7\)这一个点，出发的时候，我们找到\(4\)这一个点，同时，也是在存储的时候我们也发现\(4\)这一个点已经在\(stack\)中了，所以我们也很容易理解，从\(4 \to 7\)这一个过程经历的必然是一个强连通分量(或者说，是一个环)，相应的，很好理解， 如果我们不用\(low\)记录一下这个最小值，我们根本不知道这一个环是从什么时候开始的，所以\(low\)的重要性，也就可以体现了，我们找完了一个\((4 \to 6 \to 7)\)这一个环
![]()
这里写一个代码，更深刻的理解一下，当找到一个环的时候，也就是我们的这个\(low\)的最小值和下一次搜索出来的是一样的时候，我们把栈中\(low\)之后的全部弹出去，就记录了\(scc_i\)(第\(i\)个连通分量的大小了) ，当然当求解\((3)\)这一个连通分量也是一样的道理。
继续看一下求解\((1 \to 2 \to 5)\)这一个连通分量
我们划去已经匹配了的节点，此时的$stack : 1 , 2 $还是给图吧
![]()
我们继续寻找，略过找到\(5\)这个节点，我们还是发现，又回到原点了， 同上述的\((4 \to 6 \to 7)\)这一个环，就行了。
然后就结束了
\(Code\) :
输出全部强连通分量
#include<iostream> //输出所有强连通分量
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,x,y,top=0,cnt=0,t,sum;
int ans1=-1,ans2=-1,ans3=-1;
int d[200020];
int a[200020];
int c[200020];
int h[200020];
int dfn[200020];
int low[200020];
int stack[200020];
int scc[200020] ;
bool in[200020];
struct edge{
int u;
int v;
int w;
int next;
}e[1000020];
void Add(int u,int v)
{
++top;
e[top].u=u;
e[top].v=v;
e[top].next=h[u];
h[u]=top;
}
inline int read()
{
int x = 0 , f = 1 ; char ch = getchar() ;
while(!isdigit(ch)) { if(ch == '-') f = - 1 ; ch = getchar() ; }
while( isdigit(ch)) { x = x * 10 + ch - '0' ; ch = getchar() ; }
return x * f ;
}
void tarjan(int u) //tarjan模板
{
dfn[u] = low[u] = ++ sum ;
stack[++top] = u ;
for(int i = h[u] ; i ; i = e[i].next)
{
int v = e[i].v ;
if(!dfn[v])
{
tarjan(v) ;
low[u] = min (low[u] , low[v]) ;
}
else if (!in[v]) low[u] = min (low[u] , dfn[v] ) ;
}
if(low[u] == dfn[u])
{
in[u] = ++ cnt ;
while(stack[top + 1] != u)
{
++scc[cnt] ;
in[stack[top]] = cnt ;
printf("%d " , stack[top]) ;
top -- ;
}
printf("该连通块的大小为： %d\n" , scc[cnt]) ;
}
printf("\n") ;
}
int main()
{
n=read(); m=read();
for(int i=1;i<=m;++i)
{
x=read();
y=read();
Add(x,y);
}
for(int i=1;i<=n;++i)
if(!dfn[i]) tarjan(i);
return 0;
}
题目
有空再粘，嘻嘻，笔者略有些懒，\(QwQ\)
割点
【明确定义】：首先我们要明确一下它们的定义，
\(1.\)割点:删去这个点后，图\(G\)的连通块数目增加了(连通分量)
\(2.\)桥：同上，删去这一条边后,图\(G\)的连通块增加了
\(3.\)割点和桥是无向图中的。
根据上述的明确的定义，我们也可以明白，割点和桥都是会影响图的连通性的。
请看下图：
![]()
该图中，我们枚举删除判断过程
我们删去\(2\)这个节点，连通块不变，还是1个
删去\(1\)这个节点，连通块变为\(2\)个，所以\(1\)是一个割点
删去\(3\)这个节点，连通块不变，仍为\(1\)个，所以\(3\)不是割点
删去\(4\)这个节点，连通块变为\(2\)个，所以\(4\)是割点
删去\(5\)这个节点，连通块变为\(2\)个，所以\(5\)是割点
删去\(6\)这个节点，连通块变为\(2\)个，所以\(6\)是割点
删去\(7\)这个节点，连通块不变，仍为\(1\)个，所以\(7\)不是割点
删去\(8\)这个节点，连通块不变，仍为\(1\)个，所以\(8\)不是割点
删去\(9\)这个节点，连通块不变，仍为\(1\)个，所以\(9\)不是割点
综上， \(1,4,5,6\)是割点
复制真香
可以用下方的\(Code\)来检验一下，应该是对的。
然后我们发现，如果我们手模的话，如果不用\(copy\)，那么这9个点的复杂度，就已经让我头大了，所以，为了避免这种情况的出现，我们选择用\(Tarjan\)算法来求解割点
割点判定定理
\(x\)是割点，当且仅当搜索树上存在\(x\)的一个子节点\(v\)满足
[dfn_x <low_y ]
特别的，当\(x\)是割点，同时当且仅当搜索树上存在\(x\)的两个子节点\(v\)满足上述关系，则代表，两个子节点无法相互到达
关于证明，就百度吧，紫书也有
\(details \ \ of \ \ code\)
第一次访问到\(u\)的时候，应把 \(dfn_u = low_u\) 赋成时间戳
如果\(v\)是\(u\)的节点， 那么 \(low_u = min(low_u , low_v)\)
如果不是，那么 \(low_u = min(low_u , dfn_v)\)
和上述求强连通分量相差不大
\(Code\)
/*
by : Zmonarch
知识点 ： Tarjan
*/
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <set>
#define int long long
using namespace std ;
const int kmaxn = 1e6 + 10 ;
inline int read()
{
int x = 0 , f = 1 ; char ch = getchar() ;
while(!isdigit(ch)) { if(ch == '-') f = - 1 ; ch = getchar() ; }
while( isdigit(ch)) { x = x * 10 + ch - '0' ; ch = getchar() ; }
return x * f ;
}
int n , m ;
struct node
{
int nxt , u , v ;
}e[ kmaxn << 1] ;
int tot , h[kmaxn << 1] ;
void add(int u , int v)
{
e[++tot].nxt = h[u] ;
e[tot].u = u ;
e[tot].v = v ;
h[u] = tot ;
}
int dfn[kmaxn] , low[kmaxn] , sum , ans , cut[kmaxn << 1];
void tarjan(int u , int f)
{
dfn[u] = low[u] = ++ sum ;
int child = 0 ; //记录当前这个节点的子树个数
for(int i = h[u] ; i ; i = e[i].nxt)
{
int v = e[i].v ;
if(!dfn[v])
{
tarjan(v , u) ;
low[u] = min(low[u] , low[v]) ;
if(low[v] >= dfn[u] && u != f ) // low[v] > dfn[u]就是割边
{
cut[u] = 1 ;
}
if(u == f) child ++ ;
}
low[u] = min(low[u] , dfn[v]) ;
}
if(child >= 2 && u == f)
{
cut[u] = 1 ;
}
}
signed main()
{
n = read() , m = read() ;
for(int i = 1 ; i <= m ; i++)
{
int u = read() , v = read() ;
add( u , v );
add( v , u ) ;
}
for(int i = 1 ; i <= n ; i++)
{
if(!dfn[i])
{
tarjan(i , i) ;
}
}
for(int i = 1 ; i <= n ; i++)
{
if(cut[i]) ans ++ ;
}
printf("%d\n" , ans) ;
for(int i = 1 ; i <= n ; i++)
{
if(cut[i])
{
printf("%d " ,i ) ;
}
}
return 0 ;
}
桥
回到刚刚的哪一个图，但是 我们这次把边标号，点不标号了
如下图：
![]()
我们手模枚举删除边
删去\(1\)号边，连通块变为\(2\)个，所以，\(1\)号是割边
删去\(2\)号边，连通块不变，所以，\(2\)号不是割边
删去\(3\)号边，连通块不变，所以，\(3\)号不是割边
删去\(4\)号边，连通块不变，所以，\(4\)号是割边
删去\(5\)号边，连通块变为\(2\)个，所以，\(5\)号是割边
删去\(6\)号边，连通块变为\(2\)个，所以，\(6\)号是割边
删去\(7\)号边，连通块不变，所以，\(7\)号不是割边
删去\(8\)号边，连通块不变，所以，\(8\)号不是割边
删去\(9\)号边，连通块不变，所以，\(9\)号不是割边
最后一号边忘了标记了，算了，相当于\(7,8,9\)号边
对了，我们手模的全都是\(dfs\)求解过程，但笔者没有写过，也不会打，就放弃了，手模吧
综上所述，\(1,5,6\)是割边，其余的都不是割边
桥的判定定理
如果\((u , v)\)是割边，当且仅当\((u,v)\)在搜索树上，且在搜索树上存在\(u\)的一个子节\(v\)
满足$$dfn_u < low_v$$
证明紫书上也有
\(details \ \ of \ \ code\)
如果\(u\)是\(v\)的父节点，并且\((u,v)\)没有重边时，根据定义，不可以用\(low_u\)更新\(low_v\)
如果\(u\)是\(v\)的父节点，并且\((u,v)\)出现重边时，可以用\(low_u\)更新\(low_v\)
\(so\) , 不能简单地用\(fa\)更新节点，而可以纪录一下搜索树上的\(u\)经过的边，再\(xor\)一下出其反边，在更新的的时候不走反边就行 ----------- luckyblock
\(Code\)
输出所有的割边，也是没有模板题，和上面的差不多，但是走反边就很妙
/*
by : Zmonarch
知识点 ： Tarjan
*/
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <set>
#define int long long
using namespace std ;
const int kmaxn = 1e6 + 10 ;
inline int read()
{
int x = 0 , f = 1 ; char ch = getchar() ;
while(!isdigit(ch)) { if(ch == '-') f = - 1 ; ch = getchar() ; }
while( isdigit(ch)) { x = x * 10 + ch - '0' ; ch = getchar() ; }
return x * f ;
}
int n , m ;
struct node
{
int nxt , v , u ;
}e[kmaxn << 1] ;
int tot = 1 , h[kmaxn << 1] ;
void add(int u , int v)
{
e[++tot].nxt = h[u] ;
e[tot].v = v ;
}
int dfn[kmaxn] , low[kmaxn] , vis[kmaxn] ;
int sum , ans ;
void tarjan(int u , int f)
{
dfn[u] = low[u] = ++sum ;
for(int i = h[u] ; i ; i = e[i].nxt)
{
int v = e[i].v ;
if(!dfn[v])
{
tarjan(v , i) ;
low[u] = min (low[u] , low[v]) ;
if(low[v] > dfn[u]) //这条边是桥边
{
vis[i] = vis[i ^ 1] = 1 ;
}
}
else if(i != (f ^ 1))
{
low[u] = min (low[u] , dfn[v]) ;
}
}
}
signed main()
{
n = read() , m = read() ;
for(int i = 1 ; i <= m ; i++)
{
int u = read() , v = read() ;
add(u , v) ;
add(v , u) ;
}
for(int i = 1 ; i <= n ; i++)
{
if(!dfn[i])
{
tarjan(i , 0) ;
}
}
//printf("%d\n" , tot) ; /* printf("\n") ;
for(int i = 2 ; i < tot ; i += 2) //别忘了是双向边
{
if(vis[i])
{
printf("%d %d\n" , e[i ^ 1].v , e[i].v ) ;
}
}
return 0 ;
}
割点和桥的题目的话，我也没全\(A\)掉，终究还是菜呀，等我全\(A\)掉再放吧
双连通分量
分为点双和边双，
点双(\(BCC\))
点双： 是点双连通分量的点，什么意思呢，就是删除任意一个点，图\(G\)的连通性不发生改变。
具体是什么？怎么和这一节联系起来的。
性质
\(1.\)任意两点间至少存在两条点不重复的路径等价于图中删去任意一个点都不会改变图的连通性，即\(BCC\)中无割点
\(2.\)两个点双的公共点，就是这两个点双形成一个子图的割点(或者说是原图的割点)
\(3.\)图中一个割点一定属于至少两个点双，而一个非割点一定只属于一个点双，也就是说，割点，可以是两个以上的点双形成的公共点，但同时，一个非割点，显然，只属于一个点双。
算法
维护一个栈，遇到一个新的节点，就进栈，遇上\(low\)比他小的就退栈
注 ： 目标节点也要出栈，不能忘记
浅显的理解
首先，什么叫\(BCC\),什么玩意叫做点双呢，看一下这个图：
![]()
我也不是很清楚，到底为什么这么个玩意叫做\(BCC\),可能这一个图也根据定义，也满足，所以属于\(BCC\), 抽象的说，就是删去任意一个点不改变连通性，那么也就是满足要是个环，或者就向上面一样，其他成链，成树，成图，貌似都是不满足的。
为什么用栈实现，我为什么在这说，我也不知道
> 原因就是因为\(bcc\)和上方的强连通分量一样的 ，满足搜索树中从下到上搜索出来的，同时\(DFS\)是从上到下，那这么个反过来的数据结构，除了想到用\(stack\)，还能用啥
结论：
对于每个BCC，它在DFS树中最先被发现的点一定是割点或DFS树的树根
也等价于每个BCC都在其最先被发现的点(一个割点或树根)的子树中
> 证明 ： 割点是BCC间的交点，故割点在BCC的边缘，且BCC间通过割点连接，所以BCC在DFS树中最先被发现的点是割点；特殊情况是对于开始DFS的点属于的BCC，其最先被发现的点就是DFS树的树根
\(Code\)
我也没有找到模板题，倒是一堆\(bcc+\)缩点的，提供一下模板吧
输出所有的BCC
/*
by : Zmonarch
知识点 ： Tarjan,点双
*/
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <stack>
#define int long long
using namespace std ;
const int kmaxn = 1e6 + 10 ;
inline int read()
{
int x = 0 , f = 1 ; char ch = getchar() ;
while(!isdigit(ch)) { if(ch == '-') f = - 1 ; ch = getchar() ; }
while( isdigit(ch)) { x = x * 10 + ch - '0' ; ch = getchar() ; }
return x * f ;
}
int n , m ;
vector<int> bcc[kmaxn << 1] ; //用来储存点双
int cnt_bcc;
int num , sum ;
int dfn[kmaxn] , low[kmaxn] , f[kmaxn] ;
struct node
{
int nxt , v , u ;
}e[kmaxn << 1] ;
stack<int> st ;
int tot , h[kmaxn << 1] ;
void add(int u , int v)
{
e[++tot].nxt = h[u] ;
e[tot].u = u ;
e[tot].v = v ;
h[u] = tot ;
}
void tarjan(int u , int fa)
{
f[u] = fa ;
st.push(u) ; //搞栈里面
dfn[u] = low[u] = ++sum ;
for(int i = h[u] ; i ; i = e[i].nxt)
{
int v = e[i].v ;
if(!dfn[v])
{
tarjan(v , u) ;
low[u] = min (low[u] , low[v]) ;
if(low[v] >= dfn[u]) //割点判定定理
{
++cnt_bcc;
while(st.top() != v) //直到弹出整个bcc
{
bcc[cnt_bcc].push_back(st.top());
st.pop() ;
}
bcc[cnt_bcc].push_back(v) ; st.pop() ;
bcc[cnt_bcc].push_back(u) ;
}
}
else if(v != fa)
{
low[u] = min(low[u] , dfn[v]) ;
}
}
}
signed main()
{
n = read() , m = read() ;
for(int i = 1 ; i <= m ; i++)
{
int u = read() , v = read() ;
add(u , v) ;
add(v , u) ;
}
for(int i = 1 ; i <= n ; i++)
{
tarjan(i , i) ;
}
for(int i = 1 ; i <= cnt_bcc ; i++) //输出所有的bcc
{
printf("bcc %d :" , i) ;
for(int j = 0 ; j < bcc[i].size() ; j++)
{
printf("%d" , bcc[i][j]) ;
printf(" ") ;
}
printf("\n") ;
}
return 0 ;
}
另外，欢迎把这个\(fw\)给\(hack\)掉，当然，你不能卡着我爆空间。