Tarjan系列！我愿称Tarjan为爆搜之王！

1.Tarjan求LCA

利用并查集在一遍DFS中可以完成所所有询问。是一种离线算法。

遍历到一个点时，我们先将并查集初始化，再遍历完一个子树之后，将该子树的根的父亲指向当前点。

最后在回溯的时候给询问的答案更新一下，枚举一下 \(v\in [1,n]\) 的点，看是否有询问，如果有询问更新一下 \(LCA[u][v]=LCA[v][u]=find(v);\) 但是前提是 \(v\) 已经被访问。

我们优化一下枚举的点，放入vector优化一下，就是 \(O(n+m)\) 的复杂度了。

测试用题：

T1

T2

T1 Code:

但是经过事实证明，有速度排行：

树剖 < st表 < 倍增 < Tarjan

什么东西天下第一不用我多说了吧。

#include<bits/stdc++.h>

#define ll long long

#define db double

#define filein(a) freopen(#a".in","r",stdin)

#define fileot(a) freopen(#a".out","w",stdout)

template<class T>

inline void read(T &s){

	s=0;char ch=getchar();bool f=0;

	while(ch<'0'||'9'<ch) {if(ch=='-') f=1;ch=getchar();}

	while('0'<=ch&&ch<='9') {s=s*10+(ch^48);ch=getchar();}

	s=f?-s:s;

	if(ch=='.'){

		db p=0.1;ch=getchar();

		while('0'<=ch&&ch<='9') {s=s+(ch^48)*p;p*=0.1;ch=getchar();};

	}

}

using std::vector;

const int N=5e5+1;

int n,m,rt;

vector<int>head,nxt;

struct Edge{

	int u,v;

};vector<Edge>to;

inline void join(int u,int v){

	nxt.push_back(head[u]);

	head[u]=to.size();

	to.push_back({u,v});

}

struct ques{

	int id,x;

};

vector<ques>qu[N];

int ans[N];

int fa[N];

int find(int x){

	return x==fa[x]?x:fa[x]=find(fa[x]);

}

bool vis[N];

void dfs(int u){

	fa[u]=u;

	vis[u]=1;

	for(int i=head[u];~i;i=nxt[i]){

		int v=to[i].v;

		if(vis[v]) continue;

		dfs(v);

		fa[v]=u;

	}

	for(auto it:qu[u]){

		int id=it.id,x=it.x;

		if(vis[x]){

			ans[id]=find(fa[x]);

		}

	}

}

int main(){

	filein(b);fileot(b);

	read(n);read(m);read(rt);

	head.resize(n+1,-1);

	for(int i=1;i<n;++i){

		int u,v;read(u);read(v);

		join(u,v);join(v,u);

	}

	for(int i=1;i<=m;++i){

		int u,v;read(u);read(v);

		qu[u].push_back({i,v});

		qu[v].push_back({i,u});

	}

	dfs(rt);

	for(int i=1;i<=m;++i){

		printf("%d\n",ans[i]);

	}

	return 0;

}

T2:我们考虑树上差分即可，这个我在之前的博客提到过了，就不多说了。

树上差分

2.Tarjan求割点、割边、强连通分量

概念

割点：删除点 \(u\) 后使得连通图变为非连通图，该点为割点。

如果一个图没有割点，那么叫重连通图，每个顶点间至少2条路径(除非点数<3)。

强连通指有向图中的连通图，无向图中叫连通图。

割点

然后Tarjan可以在DFS中完成割点查找。我们给点赋予时间戳 \(dfn\) ，就得到了深度优先生成树。

我们称能到达 \(dfn\) 小于自己的边叫回边。

而对于一个点 \(u\) 要么是根要么非根。先考虑 \(u\) 为根，若其为割点，其满足拥有两个及以上的子树。这个结论是显然的，可以用链和一颗根有多个儿子的树来举例分析。

如果 \(u\) 不是根，\(u\) 为割点，那么其子树中存在有的点没有到达 \(u\) 祖先的回边。

因为没有回边到达 \(u\) 以上，那么删除这个点 \(u\) 之后必定能使得图非联通。(具体就是这个点出不去了)

考虑怎么判断这个条件。我们用时间戳 \(dfn\) 和最低时间戳 \(low\) 来辅助。

其中:

\[low[u]=min\{dfn[u],min\{low[v]|v是u的儿子\},min\{dfn[v]|(u,v)为一条回边\}\}
\]

那为什么 \(low\) 取不到 \(min\{low[v]|(u,v)为一条回边\}\) ? 原因其实很简单，首先是要根据其定义，然后就考虑为什么这样设计。比如说当我们求割点的时候，割点可以通过回边到达一个 \(dfn\) 更小的点，但是我们既然删掉了这个点那就不影响了。如果这是其子树正好有到达 \(u\) 点的回边，如果随着其 \(low\) 跳到那个更低的点，那么结果是有问题的，这是会把 \(u\) 误判为非割点。

再考虑这样设计为什么不会错，因为我们这样已经足够判断其是否会通向其他子树了。

  • 在 \(u\) 非 \(dfn\) 树上的根时，若存在 \(v\) 是 \(u\) 的儿子，使 \(dfn[u]<=low[v]\) ,那么 \(u\) 是割点。

考虑反证，若 \(low[v]<dfn[u]\) ,那么子树中必定有向 \(u\) 祖先的回边，因此 \(u\) 非割点。

然后考虑一下根有多个子树的情况即可。

#include<bits/stdc++.h>

#define ll long long

#define db double

#define filein(a) freopen(#a".in","r",stdin)

#define fileot(a) freopen(#a".out","w",stdout)

template<class T>

inline void read(T &s){

	s=0;char ch=getchar();bool f=0;

	while(ch<'0'||'9'<ch) {if(ch=='-') f=1;ch=getchar();}

	while('0'<=ch&&ch<='9') {s=s*10+(ch^48);ch=getchar();}

	s=f?-s:s;

	if(ch=='.'){

		db p=0.1;ch=getchar();

		while('0'<=ch&&ch<='9') {s=s+(ch^48)*p;p*=0.1;ch=getchar();};

	}

}

using std::vector;

const int N=2e4+1;

vector<int>head,nxt;

struct Edge{

	int u,v;

};vector<Edge>to;

int n,m;

inline void join(int u,int v){

	nxt.push_back(head[u]);

	head[u]=to.size();

	to.push_back({u,v});

}

int idx;

int dfn[N],low[N];bool cut[N];

void dfs(int u,int f){

	dfn[u]=low[u]=++idx;

	int child=0;

	for(int i=head[u];~i;i=nxt[i]){

		int v=to[i].v;

		if(!dfn[v]){

			dfs(v,u);

			if(dfn[u]<=low[v] and u!=f){

				cut[u]=1;

			}

			low[u]=std::min(low[u],low[v]);

			if(u==f) ++child;

		}else if(v!=f){

			low[u]=std::min(low[u],dfn[v]);

		}

	}

	if(child>=2 and u==f){

		cut[u]=1;

	}

}

int main(){

	filein(b);fileot(b);

	read(n);read(m);

	head.resize(n+1,-1);

	for(int i=1;i<=m;++i){

		int u,v;read(u);read(v);

		join(u,v);join(v,u);

	}

	for(int i=1;i<=n;++i){

		if(!dfn[i]){

			idx=0;

			dfs(i,i);

		}

	}

	int ans=0;

	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);

		}

	}putchar('\n');

	return 0;

}

割边

删掉一条边后连通图变为非联通的，那么这条边称为割边(或桥)。

在 \(dfs\) 树上，\(u\) 为 \(v\) 的父亲节点，那么 \((u,v)\) 是割边的条件为：\(u\) 到 \(v\) 的边不是重边且 \(v\) 及其子孙节点中没有向 \(u\) 及其祖先的回边。

因为这次删的是边，而不是点，所以不能反到 \(u\)，不等式不能取到等号。

类似的,若 \(dfn[u]<low[v]\),那么 \((u,v)\) 是割边。

由于没有模板再加上和上面的类似，我就只写核心代码了。

void dfs(int u){

	dfn[u]=low[u]=++idx;

	for(int i=head[u];~i;i=nxt[i]){

		int v=to[i].v;

		if(!dfn[v]){

			dfs(v);

			if(dfn[u]<low[v]){

				cut[i]=1;

			}

			low[u]=std::min(low[u],low[v]);

		}else if(v!=f){

			low[u]=std::min(low[u],dfn[v]);

		}

	}

}

割点与割边

  • 两个割点之间的边是割边吗。割边的两个端点是割点吗。

举反例即可。第一很显然是错的，因为我们断掉一个点和断掉一条边是不等价的，上面我们论证 \(low\) 的时候举了这样的例子，就不多赘述了。第二个我们发现也是有问题的，虽然我们断点的时候肯定会断掉这条边，显然如果那边的点在删完这个点之后删空了，那么也是不满足的。

强连通分量

有向图各个节点互相可达，那么叫做强连通分量。

一遍DFS求出。若有节点 \(u\) 满足 \(low[u]==dfn[u]\) 那么其子树不可能到达其祖先。那么这个 \(u\) 为一个强连通分量在 \(dfs\) 搜索树中的根。其中有多个强连通分量，其子树与一个强连通分量不一定完全相等。我们递归将其下的强连通分量记录并去除，最后以 \(a\) 为根又有一个强连通分量。

其下的强连通分量按照相同方法找到。

我们用栈来找出一个强连通分量中的点(弹出其下的强连通分量中的点,一直弹到弹掉其下强连通分量的根为止)。

代码我们和缩点一起给出。

缩点

强连通分量内可以进行缩点，然后形成DAG(有向无环图)。能有更多优秀的性质。

缩点我们给同一个强连通分量内的点染成同一色，然后检查每条边的两边的点的颜色。同色忽略，异色就对于两个颜色建一条边即可完成缩点。

以模板题T1为例

我们这个时候处理回边的方法需要修改一下。因为是有向图。我们设立一个标记看一个点是否在栈中，如果在栈中那么其为回边，否则不为回边(因为对方已经被分入一个强连通分量中)。

缩点后变为DAG，就可以使用拓扑排序了。

基本的拓扑排序不难，看一眼就会了

拓扑排序

T1

T2

#include<bits/stdc++.h>

#define ll long long

#define db double

#define filein(a) freopen(#a".in","r",stdin)

#define fileot(a) freopen(#a".out","w",stdout)

template<class T>

inline void read(T &s){

	s=0;char ch=getchar();bool f=0;

	while(ch<'0'||'9'<ch) {if(ch=='-') f=1;ch=getchar();}

	while('0'<=ch&&ch<='9') {s=s*10+(ch^48);ch=getchar();}

	s=f?-s:s;

	if(ch=='.'){

		db p=0.1;ch=getchar();

		while('0'<=ch&&ch<='9') {s=s+(ch^48)*p;p*=0.1;ch=getchar();};

	}

}

using std::vector;

const int N=1e4+1,M=1e5+1;

int n,m;

int a[N];

vector<int>head,nxt;

struct Edge{

	int u,v,w;

};vector<Edge>to;

Edge e[M];

inline void join(int u,int v){

	nxt.push_back(head[u]);

	head[u]=to.size();

	to.push_back({u,v});

}

int idx;

int dfn[N],low[N];

int st[N],top;

int col[N];

int num;

int sum[N];

bool ink[N];

void dfs(int u){

	dfn[u]=low[u]=++idx;

	st[++top]=u;

	ink[u]=1;

	for(int i=head[u];~i;i=nxt[i]){

		int v=to[i].v;

		if(!dfn[v]){

			dfs(v);

			low[u]=std::min(low[u],low[v]);

		}else if(ink[v]){

			low[u]=std::min(low[u],dfn[v]);

		}

	}

	if(low[u]==dfn[u]){

		++num;

		while(1){

			col[st[top] ]=num;

			sum[num]+=a[st[top] ];

			ink[st[top] ]=0;

			//printf("%d ",st[top]);

			if(st[top]==u){

				--top;

				//printf("(%d)",sum[num]);

				//putchar('\n');

				break;

			}

			--top;

		}

	}

}

int res=0;

void dfs2(int u){

	res+=sum[u];

	for(int i=head[u];~i;i=nxt[i]){

		int v=to[i].v;

		dfs(v);

	}

}

int dp[N];

int ind[N];

std::queue<int>q;

int ans=0;

inline void topo(){

	for(int i=1;i<=num;++i){

		if(!ind[i]){

			dp[i]=sum[i];

			ans=std::max(dp[i],ans);

			q.push(i);

		}

	}

	while(!q.empty() ){

		int u=q.front();q.pop();

		for(int i=head[u];~i;i=nxt[i]){

			int v=to[i].v;

			--ind[v];

			if(ind[v]==0){

				dp[v]=dp[u]+sum[v];

				q.push(v);

				ans=std::max(ans,dp[v]);

			}

		}

	}

}

inline bool cmp(Edge x,Edge y){

	if(x.u==y.u) return x.v<y.v;

	return x.u<y.u;

}

int main(){

	filein(b);fileot(b);

	read(n);read(m);

	head.resize(n+1,-1);

	for(int i=1;i<=n;++i){

		read(a[i]);

	}

	for(int i=1;i<=m;++i){

		int u,v;read(u);read(v);

		join(u,v);

	}

	for(int i=1;i<=n;++i){

		if(!dfn[i]){

			idx=0;

			dfs(i);

		}

	}

	m=0;

	for(int i=0;i<to.size();++i){

		if(col[to[i].u]!=col[to[i].v]){

			e[++m]={col[to[i].u],col[to[i].v]};

		}

	}

	head.clear();nxt.clear();to.clear();

	head.resize(num+1,-1);

	std::sort(e+1,e+1+m,cmp);

	for(int i=1;i<=m;++i){

		if(i>1 and e[i].u==e[i-1].u and e[i].v==e[i-1].v)

			continue;

		//printf("%d %d\n",e[i].u,e[i].v);

		join(e[i].u,e[i].v);

		++ind[e[i].v];

	}

	topo();

	printf("%d\n",ans);

	return 0;

}

最新文章

  1. HTML: vertical algin Big/small div in same row (bootstrap)
  2. Selenium_Selenium WebDriver 中鼠标和键盘事件分析及扩展
  3. HID高级攻击姿势：利用PowerShell脚本进行文件窃取
  4. hdu 5172 GTY&#39;s gay friends
  5. 关于TFTLCD硬件接口和驱动的问题
  6. 【C++学习之路】派生类的构造函数（二）
  7. SQLite数据库查看工具(免费)
  8. 搭建ubuntu版hadoop集群
  9. Java7中的ForkJoin并发框架初探（下）—— ForkJoin的应用
  10. 委托与lambda关系
  11. Python中的eval(),exec()以及其相关函数
  12. vue中展示数据
  13. Kafka（三）-- Kafka主要参数
  14. C#窗体内嵌外部程序(cmd.exe)的显示【转载】
  15. 数据库面试题之PL/SQL面试题
  16. Axios介绍和使用
  17. BZOJ3631：[JLOI2014]松鼠的新家——题解
  18. java===java基础学习（4）---字符串操作
  19. jq学习笔记（一）
  20. mui 选项卡

热门文章

  1. Day10 - JS 实现 Checkbox 中按住 Shift 的多选功能
  2. JS 实现权限列表移动
  3. 序列化和反序列化为什么要实现Serializable接口？（史上最全、简单易懂）
  4. 用户USER_HZ与内核HZ的值
  5. linux centos 8.2 安装docker
  6. GRPC-go版本
  7. 迷惑小错 之 ：requests.exceptions.ProxyError
  8. 一篇文章带你搞懂InnoDB的索引｜结合样例
  9. c#中判断类是否继承于泛型基类
  10. 论文解读（SelfGNN）《Self-supervised Graph Neural Networks without explicit negative sampling》