tarjan全家桶

tarjan 全家桶

关于tarjan 它太强了 CCCOrz

dfs树&low

dfs树：在图上做不重复经过同一点的dfs，经过的边与点形成一棵树。于是图上所有点都被这棵树包含，一部分边被包含。称被包含的点叫树边，其他边叫回边。整个图就是dfs树，由于是由dfs得到。所以dfs树有非常强的性质，所有回边一定是从一点开始，到它的一个祖先，也就是说两棵没有交集的子树之间一定没有边相连。
dfn：dfn[now]表示now点的dfn序。
low：在做tarjan算法时通常需要开一个low数组，low的定义在处理不同问题时可能略有区别。大体为low[rt]表示以rt为根的子树中经过树边和一条回边能到达的dfn最小的点的dfn。

其实理解tarjan的最好办法就是感性

强连通分量

void tarjan(int now)

{

	dfn[now]=low[now]=++tot;

	s.push(now);in[now]=1;

	for(int i=head[now];i;i=nxt[i])

	{

	    if(!dfn[to[i]])

			tarjan(to[i]),low[now]=min(low[to[i]],low[now]);

		else if(in[to[i]])

			low[now]=min(dfn[to[i]],low[now]);

	}

	if(low[now]==dfn[now])

	{

		color++;

		while(in[now])

		{

			in[s.top()]=0;

			col[s.top()]=color;

			ac[color]+=a[s.top()];

			s.pop();

		}

	}

}

割点

void tarjan(int now,int fa)

{

	low[now]=dfn[now]=++cnt;

	int son=0;

	for(int i=head[now];i;i=nxt[i])

	{

		int v=to[i];

		if(!dfn[v])

		{

			tarjan(v,now);

			low[now]=min(low[now],low[v]);

			if(low[v]>=dfn[now]&&fa!=now)

				is[now]=1;

			son++;

		}

		else low[now]=min(low[now],dfn[v]);

	}

	if(fa==now&&son>=2)

		is[now]=1;

}

双连通分量（圆方树）

void tarjan(int now)///建立圆方树

{

	dfn[now]=low[now]=++dfc;

	stk[++tp]=now;

	++tot;

	for(int i=0;i<e[now].size();i++)

	{

		int to=e[now][i];

		//cout<<"qwq"<<' '<<now<<' '<<to<<endl;

		if(!dfn[to])

		{

			//cout<<"in"<<' '<<to<<endl;

			tarjan(to);

			//cout<<"out"<<' '<<now<<' '<<to<<' '<<low[to]<<endl;

			low[now]=min(low[now],low[to]);

			if(low[to]==dfn[now])///now就是桥

			{

				cnt++;///方点+1

				for(int x=0;x!=to;--tp)///由于桥可能同时在多个双连通分量内，所以now不出栈

				{

					x=stk[tp];

					v[cnt]++;

					t[cnt].push_back(x);

					t[x].push_back(cnt);///连接方点和圆点

				}

				t[now].push_back(cnt);

				t[cnt].push_back(now);

				v[cnt]++;

			}

		}

		else ///由于是双向边，此时to[i]必然是i的父节点，根据low的定义无需考虑to[i]。

			low[now]=min(low[now],dfn[to]);

          }

}

巴特西

tarjan全家桶

tarjan 全家桶

dfs树&low

强连通分量

割点

双连通分量（圆方树）

最新文章

热门文章