脚本宝典收集整理的这篇文章主要介绍了tarjan 与强连通分量，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

前言

本文口胡。

正文

强连通分量

在有向图 D 中，如果存在一条 (u) 到 (v) 的路径，且也存在一条由 (v) 到 (u) 的路径，则称这两个点强连通。

如果这个有向图 D 中所有点强连通，则称这个图为强连通图。

而有向非联通图的极大强连通子图，则叫做强连通分量。

缩点

如果一个有向图中存在环，那么就可以把这个环缩成一个点，即缩点。

缩点和强连通分量

我们想一想，在有向环中，是不是任意一个 (u)，都可以到达任意一个 (v)，

所以这个环就是整个图的强连通子图。

我们再想一下如果如果一个环套一个环，那么这其实可以看做一个环，而在代码中也如此。

所以，用 Tarjan 求出的环，必然是图中的极大子环，所以这个环就是强连通分量。

Tarjan 求缩点

变量：

• (dfn_i)：(i) 的 dfs 序；

• (low_i)：(i) 所能访问到的最小 dfs 序；

• (dfncnt)：dfs 序计数；

• (scc_i)：(i) 所属的强连通分量；

• (sccnum)：强连通分量计数；

• (s)：手膜栈数组；

• (top)：栈的深度；

First：为什么要用栈？

很简单，如果用队列，那么当搜到一个点 (x) 是环的起点（自创概念，下面会提）时，就要依次去回头染色所访问到的节点直到 (x)（因为一个点是环的起点那么它就一定是这个环的所有节点中第一个入栈的），而队列首先访问到的是整个图第一个被访问到的节点，不符合要求，而栈就可以进行回头去染色。

Second:代码实现

首先我们可以打出来一个框架，以此 dfs 图中每一个节点，如果其中有节点的 (dfn) 为 (0)，就搜他，回溯更新 (low)，如下：

void tarjan(int x) {
    dfn[x]=low[x]=++dfncnt;//low[x] 最开始要初始化自己成自己，在之后更新
    for (int i=head[x];i;i=e[i].next) {
        int y=e[i].to;
        if (!dfn[y]) {
            tarjan(y);
            low[x]=min(low[x],low[y]);//更新low
        }
    }
}

我们再想什么情况下，(x) 为环的起点，没错可其访问到的最小点的为自己的点为环的起点。

为什么呢，我们想一想，因为 (dfncnt) 是不断增加的，所以越往后的点的 dfs 序越大，而环呢最终会回到一个被访问过的点上，而这个点就是环的起点，所以代码可改为：

void tarjan(int x) {
    dfn[x]=low[x]=++dfncnt;
    s[++top]=x;//入队
    for (int i=head[x];i;i=e[i].next) {
        int y=e[i].to;
        if (!dfn[y]) {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
    }
    if (low[x]==dfn[x]) {//环的起点
        sccnum++;//计数
        while (s[top+1]!=x) {//因为 x 也需要染色
            int y=s[top--];
            scc[x]=sccnum;
        }
    }
}

我们再想，如果一个点被访问过，并且不在任何强连通分量中，那么，我们也需要更新 (low) ，因为他的 (dfn) 是不确定的，所以代码可改为：

void tarjan(int x) {
    dfn[x]=low[x]=++dfncnt;
    s[++top]=x;//入队
    for (int i=head[x];i;i=e[i].next) {
        int y=e[i].to;
        if (!dfn[y]) {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        } else if (!scc[y]) 
            low[x]=min(low[x],dfn[y]);
    }
    if (low[x]==dfn[x]) {//环的起点
        sccnum++;//计数
        while (s[top+1]!=x) {//因为 x 也需要染色
            int y=s[top--];
            scc[x]=sccnum;
        }
    }
}

所以 Tarjan 算法就成型了。

例题

B3609

和板子差不多，但由于要求每个点所在哪个强连通分量，所以要再开一个，vector 存储，即在 Tarjan 最后的 if 中加上，一个 v[i].push_back(scccnum);，v[i] 为 (i) 属于哪个强连通分量。

代码：

//无注释
#include <algorithm>
#include <iostream>
#include <vector>

#define N 10001
#define M 100001

using namespace std;
int n,m,cnt,dfncnt,sccnum;
int head[N],scc[M];
int dfn[N],low[N];

struct Node{
	int to,next;
}e[M];

void add(int t1,int t2) {e[++cnt]=(Node){t2,head[t1]},head[t1]=cnt;}

int s[M],top;
vector<int> v[N];
int vis[N];

void tarjan(int x) {
	s[++top]=x;
	dfn[x]=low[x]=++dfncnt;
	for (int i=head[x];i;i=e[i].next) {
		int y=e[i].to;
		if (!dfn[y]) {
			tarjan(y);
			low[x]=min(low[x],low[y]);
		} else if (!scc[y]) 
			low[x]=min(low[x],dfn[y]);
	}
	if (dfn[x]==low[x]) {
		sccnum++;
		while (s[top+1]!=x) {
			int y=s[top];
			scc[y]=sccnum;
			v[sccnum].push_back(y);
			top--;
		}
	}
}

int main() {
	cin>>n>>m;
	for (int i=1,t1,t2;i<=m;i++) {
		cin>>t1>>t2;
		add(t1,t2);
	}
	for (int i=1;i<=n;i++)
		if (!dfn[i]) tarjan(i);
	cout<<sccnum<<endl;
	for (int i=1;i<=n;i++) {
		if (vis[scc[i]]) continue;
		vis[scc[i]]=1;
		sort(v[scc[i]].begin(),v[scc[i]].end());
		for (int j=0;j<v[scc[i]].size();j++) {
			cout<<v[scc[i]][j]<<" ";
		}
		cout<<endl;
	}
}

finally

咕咕咕。

脚本宝典总结

以上是脚本宝典为你收集整理的tarjan 与强连通分量全部内容，希望文章能够帮你解决tarjan 与强连通分量所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。