title: 'tarjan学习笔记'
date: 2022-12-30 15:00:56
tags: [学习笔记]
published: true
hideInList: false
feature:
isTop: false
1.概念
- 强连通分量：在有向图或无向图中的点集，保证集合中每两个点都可以互相到达。
- 割点：一个点是割点当且仅当删除这个点之后连通块的数量会增加。
- 桥：一条边是桥当且仅当删除这条边后连同快的个数会增加。
- 树边：遍历一个图时的dfs树上的边。
- 非树边：图中除了树边以外的其他边。
- dfn：时间戳，即dfs一个图时点是第几个被遍历到的。
- low：子树内所有节点所能通过走非树边到的点的dfn的最小值。
2.算法
tarjan的算法本质其实就是在dfs图的时候求dfn和low这两个值，通过这两个值可以求出很多东西，详见应用。
对于dfn很好处理，在dfs时直接记录即可。对于 $low_x$，以及现在有一条 $(x,y)$ 的边，如果 $y$ 还没有遍历过，说明这是树边，$y$ 是 $x$ 子树内的节点，所以 $low_x=\min{low_x,low_y}$。如果 $y$ 已经遍历过了，则这条边为非树边（此时 $y$ 有可能为 $x$ 的父亲，因为可能有重边）或者树边（此时 $y$ 必定 $x$ 的父亲）。如果是非树边的话 $low_x=\min{low_x,dfn_y}$。
3.应用
3-1割点
如果一个点是割点，那么他的任意一个儿子的子树内的点都不会不经过这个点到达 $dfn$ 较小的点（即这个点的祖先），那么如果将这个点删去，这个点的某儿子的子树将会与自己的祖先断开。
模板
#include<bits/stdc++.h>
using namespace std;
const int maxn=20010;
int n,m,cnt=1,tim,rt,t[maxn],dfn[maxn],low[maxn],head[maxn];
vector<int>ans;
bool vis[maxn];
struct E{
int to,next;
}edge[maxn*20];
void add(int u,int v){
edge[++cnt].to=v;edge[cnt].next=head[u];head[u]=cnt;
}
void tarjan(int x,int re){
dfn[x]=low[x]=++tim;
int flag=0;
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(!dfn[y]){
tarjan(y,i);
low[x]=min(low[x],low[y]);
if(dfn[x]<=low[y]){
if(vis[x])continue;
if(x!=rt)ans.push_back(x),vis[x]=1;
else if(flag>=1)ans.push_back(x),vis[x]=1;
flag++;
}
}else low[x]=min(low[x],dfn[y]);
}
return;
}
int main(){
ios::sync_with_stdio(false);
std::cin.tie(0);std::cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
add(u,v);add(v,u);
}
for(int i=1;i<=n;i++){
tim=0;rt=i;
if(!dfn[i])tarjan(i,0);
}
for(int i=1;i<=n;i++)if(t[i]>=2)ans.push_back(i);
cout<<ans.size()<<endl;
sort(ans.begin(),ans.end());
unique(ans.begin(),ans.end());
for(int x:ans)cout<<x<<' ';
return 0;
}
3-2桥
如果一条是桥，那么它肯定是树边。因为删掉任意一条非树边，点仍然可以通过树边相连，因此不会增加连通块的数量。而对于x指向y的树边 $(x,y)$，如果它是桥，那么y不能”绕开“ $(x,y)$ 这条边，所以y可以到的最小的点的dfn值必然会大于x。
模板。
#include<bits/stdc++.h>
using namespace std;
const int maxn=20010;
int n,m,cnt=1,tim,rt,dfn[maxn],low[maxn],head[maxn];
vector<pair<int,int> >ans;
bool vis[maxn];
struct E{
int from,to,next;
}edge[maxn*20];
void add(int u,int v){
edge[++cnt].to=v;edge[cnt].from=u;
edge[cnt].next=head[u];head[u]=cnt;
}
void tarjan(int x,int re){
dfn[x]=low[x]=++tim;
int flag=0;
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(!dfn[y]){
tarjan(y,i);
low[x]=min(low[x],low[y]);
if(dfn[x]<low[y]){
pair<int,int>tmp=make_pair(edge[i].from,edge[i].to);
if(tmp.first>tmp.second)swap(tmp.first,tmp.second);
if(x!=rt||flag>=1)ans.push_back(tmp);
flag++;
}
}else if(re!=(i^1))low[x]=min(low[x],dfn[y]);
}
return;
}
int main(){
ios::sync_with_stdio(false);
std::cin.tie(0);std::cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
add(u,v);add(v,u);
}
tarjan(1,0);
sort(ans.begin(),ans.end());
for(pair<int,int> x:ans)cout<<x.first<<' '<<x.second<<endl;
return 0;
}
3-3缩点
对于一个有向图，每个强连通分量可以缩为1个点，使得原图变为一个有向无环图。
先叙述过程在解释原理：我们维护一个栈，每dfs到一个点就入栈，如果我们dfs到了 $x$，回溯时如果 $dfn_x=low_x$ 那么就将 $x$ 及 $x$ 的上方的点出栈，这些点构成一个强连通分量。
原理：那么在每个点回溯时，每个点及其栈中上方的所有点构成了这个点的子树，如果 $dfn_x=low_x$ 那么意味着子树内每个点都无法通过非树边到达 $dfn$ 更小的点。我们设栈中 $x$ 上方的点构成集合 $S$。对于 $y \in S$ 我们有结论：
- $low_y=x$ ：因为 $low_x==dfn_x$ 所以根据定义 $low_y \ge dfn_x$。但是如果 $low_y>dfn_x$ 的话，$dfn=low_y$ 的点回溯时就将 $y$ 从栈中弹出了，因此 $low_y=dfn_x$。
既然 $low_y=dfn_x$ 那么 $y$ 肯定能通过非树边走到 $x$，也就是子树内出现了环。所以 $y$ 与 $x$ 在同一强连通分量中，且 $dfn_x$ 为该强连通分量中最小的。
具体地，我们再举个例子。
在该图中，$(1,2) , (2,5) , (5,6) , (2,3)$ 是树边，而 $4$ 号点与其他点不连通。
我们从1号点开始dfs，我们会dfs到2，然后dfs到5，再dfs到6。
此时6无法走到任何地方，于是开始回溯，因为 $low_6=dfn_6$ 且6在栈顶，所以6单独为1个强连通分量。
接下来我们回溯到5，此时 $low_5=\min{low_5,low_6}=5=dfn_5$ 且5在栈顶，所以5单独为一个强联通分量。
接下来我们回到2，继续dfs到3，这时，3有一条到1的非树边，所以 $low_3=\min{low_3,dfn_1}=1$，然后回溯到2。$low_2=\min{low_2,low_3}=1$，$low_2 \ne dfn_2$ 所以继续回溯。
回溯到1，因为 $low_1=dfn_1$ 所以1,2,3为一个强连通分量。
模板
只需要记录每个强连通分量的大小即可。
4.练习
受欢迎的牛
缩点后每个点的奶牛必然互相爱慕，所以缩点后的点如果有仅有一个出度为0的点，那么这个点的所有牛都是明星牛。所以我们再tarjan的时候需要记录强连通分量的大小。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=100010,maxm=200010;
int head[maxn],low[maxn],dfn[maxn],stack[maxn],size[maxn];
int cd[maxn],id[maxn];
int top,tot,cnt,n,m,col;
bool vis[maxn];
struct E{
int to,next,from;
}edge[maxm];
vector<int>g[maxn];
void add(int u,int v){
edge[++cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;edge[cnt].from=u;
}
void tarjan(int x){
dfn[x]=low[x]=++tot;
stack[++top]=x;
vis[x]=1;
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}else if(vis[y])low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x]){
int y;++col;id[x]=col;
while(y=stack[top--]){
vis[y]=0;
size[col]++;
id[y]=col;
if(x==y)break;
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
}
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
for(int i=1;i<=m;i++){
if(id[edge[i].from]!=id[edge[i].to]){
cd[id[edge[i].from]]++;
}
}
int sum=0,ans=0;
for(int i=1;i<=col;i++)if(!cd[i])sum++,ans=size[i];
printf("%d\n",sum==1?ans:0);
return 0;
}
校园网
对于缩完点的图。
- 任务A：入度为0的点没有点给他软件，所以需要自己得到软件副本，所以答案为入度为0的点的数量。
- 任务B：我们直接将出度为0的点连给入度为0的点，因此答案就是出度为0的点和入度为0的点数的更大值。
#include<bits/stdc++.h>
using namespace std;
const int maxn=5010;
int n,m,cnt,tim,ans,res;
int f[maxn],rd[maxn],cd[maxn],dfn[maxn],low[maxn],head[maxn];
bool vis[maxn];
stack<int>s;
queue<int>q;
struct E{
int from,to,next;
}edge[maxn];
void add(int u,int v){
edge[++cnt].to=v;edge[cnt].from=u;edge[cnt].next=head[u];head[u]=cnt;
}
int find(int x){
if(x==f[x])return x;
else return f[x]=find(f[x]);
}
void tarjan(int x){
dfn[x]=low[x]=++tim;
s.push(x);vis[x]=1;
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}else if(vis[y])low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
while(s.top()!=x){
f[s.top()]=x;
vis[s.top()]=0;
s.pop();
}vis[x]=0;s.pop();
}
return;
}
int main(){
ios::sync_with_stdio(false);
std::cin.tie(0);std::cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
int y;cin>>y;f[i]=i;
while(y!=0){
add(i,y);
cin>>y;
}
}
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i);
}
for(int i=1;i<=cnt;i++){
int u=edge[i].from,v=edge[i].to;
int fx=find(u),fy=find(v);
if(fx==fy)continue;
rd[fy]++;cd[fx]++;
}
for(int i=1;i<=n;i++)if(f[i]==i&&rd[i]==0)ans++;
cout<<ans<<endl;
for(int i=1;i<=n;i++)if(f[i]==i&&cd[i]==0)res++;
int tmp=0;
for(int i=1;i<=n;i++)tmp+=f[i]==i;
if(tmp==1)cout<<0;
else cout<<max(ans,res);
return 0;
}