Tarjan算法

本篇博客基于OI-Wiki进行了摘录，详细版请点链接

算法应用：求解有向图的强连通分量
Tarjan算法涉及的变量：

d f n u dfn_{u} dfnu​: 深度优先搜索遍历时结点 u u u被搜索的次序 l o w u low_{u} lowu​: 能够回溯到的最早的已经在栈中的结点。设以 u u u为根的子树为 s u b t r e e u subtree_{u} subtreeu​。 l o w u low_{u} lowu​定义为以下结点的 d f n dfn dfn的最小值： s u b t r e e u subtree_{u} subtreeu​中的结点；从 s u b t r e e u subtree_{u} subtreeu​ 通过一条不在搜索树上的边能到达的结点。

一个结点子树内结点的 d f n dfn dfn都大于该结点 d f n dfn dfn
从根开始的一条路径上的 d f n dfn dfn严格递增， l o w low low严格非降
按照深度优先搜索算法搜索的次序对图中所有的结点进行搜索。在搜索过程中，对于结点 u u u和与其相邻的结点 v v v（ v v v不是 u u u的父节点）考虑 3 种情况：

v v v未被访问：继续对 v v v进行深度搜索。在回溯过程中，用 l o w v low_{v} lowv​更新 l o w u low_{u} lowu​。因为存在从 u u u到 v v v的直接路径，所以 v v v能够回溯到的已经在栈中的结点， u u u也一定能够回溯到。 v v v被访问过，已经在栈中：根据 low 值的定义，用 d f n v dfn_{v} dfnv​更新 l o w u low_{u} lowu​。 v v v被访问过，已不在栈中，说明 v v v已搜索完毕，其所在连通分量已被处理，所以不用对其做 *** 作。

对于一个连通分量图，在该连通图中有且只有一个u使得 d f n u = l o w u dfn_{u} = low_{u} dfnu​=lowu​。
该结点一定是在深度遍历的过程中，该连通分量中第一个被访问过的结点，因为它的 dfn 和 low 值最小，不会被该连通分量中的其他结点所影响。
因此，在回溯的过程中，判定 d f n u = l o w u dfn_{u}=low_{u} dfnu​=lowu​是否成立，如果成立，则栈中 u u u及其上方的结点构成一个 SCC。

SCC:Strongly Connected Components 强连通分量

// OI-Wiki板子基础上进行修改，用了点容器
#include

using namespace std;

#define ll long long
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define de(x) cout <<':' << x << endl

const int N = 1e5+5;

int dfn[N], low[N], dfncnt;
bool in_stack[N];
int scc[N], sc;//结点i所在的SCC的编号
int sz[N];     //强连通分量i的大小

stack s;
vector g[N];

void init()
{
    dfncnt = sc = 0;
    for(int i=0;i 
算法应用 
NC15707 连通性 
题目链接
 使用tarjan算法进行缩点 *** 作，将每一个强连通分量视作一个点，找出所有入度为0的点即可。
 问：为什么不能直接找入度为0的点？
 答：可能存在情况，所有点入度都不为0，此时无法得到正确答案。
 代码：
 
#include

using namespace std;

#define ll long long
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define de(x) cout <<':' << x << endl

const int N = 1e5+5;

int dfn[N], low[N], dfncnt;
bool in_stack[N], in[N];
int scc[N], sc;//结点i所在的SCC的编号
int sz[N];     //强连通分量i的大小

stack s;
vector g[N];

void init()
{
    dfncnt = sc = 0;
    for(int i=0;i ans;
    for(int i=1;i<=n;++i)
    {
        if(!in[scc[i]])
        {
            ans.push_back(i);
            in[scc[i]] = true;
        }
    }
    printf("%dn",ans.size());
    for(int i=0;i					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5715150.html