【hh大神的】Tarjan + 缩点 模板

本文主要是介绍【hh大神的】Tarjan + 缩点 模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

此模板来自 notonlysuccess

原文链接：

http://www.notonlysuccess.com/index.php/tarjan/

大神就是吊啊。

不多说了，想学tarjan ，资料网上是有一堆的

怎么说。。我现在理解的还不算太透彻，但用模板总行吧

这里只存一下模板

使用时注意清空和存图！

（基于个人习惯，稍微有些小改动）

#define M 20001
vector <int> edge[M];//原图的边
vector <int> now[M];//新图的边
int hash[M];//用来hash新图的重边
bool vis[M];//有无访问过该点
int dfn[M],Index;//访问顺序
int low[M];//能追溯到的最早的次序
int idx[M];//点在新图的ID
int ss[M],top;//放节点的栈
bool InStack[M];//元素是不是在栈里
int n;//原图大小
int nn;//新图大小void dfs(int u) {vis[u] = true;dfn[u] = low[u] = Index ++;InStack[u] = true;ss[++top] = u;FF(i,SZ(edge[u])) {int v = edge[u][i];if(!vis[v]) {dfs(v);checkmin(low[u] , low[v]);} else if(InStack[v]) {checkmin(low[u] , dfn[v]);}}if(dfn[u] == low[u]) {int v = -1;nn++;while(u != v) {v = ss[top--];InStack[v] = false;idx[v] = nn;}}
}void Trajan() {FF(i,maxm) now[i].clear();CC(vis,false);Index = 1;top = 0;nn = 0;FF(i,n) {if(vis[i])	continue;dfs(i);}CC(hash,-1);FF(i,n) {FF(j,SZ(edge[i])) {int v = edge[i][j];if(idx[i] != idx[v] && hash[idx[i]] != idx[v]) {hash[idx[i]] = idx[v];now[idx[i]].push_back(idx[v]);}}}
}

这篇关于【hh大神的】Tarjan + 缩点 模板的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---