分类信息网站做推广,政务网站建设规划,网站建设 自助建站,做运营需要具备什么能力Tarjan算法可以应用在求解 强连通分量#xff0c;缩点#xff0c;桥#xff0c;割点#xff0c;双连通分量#xff0c;LCA等 关于文章目录强连通分量代码题目tarjan求割点割点概念流程代码#xff1a;求无向图的割边#xff0f;桥理解#xff1a;代码#xff1a;强连通…Tarjan算法可以应用在求解 强连通分量缩点桥割点双连通分量LCA等 关于
文章目录强连通分量代码题目tarjan求割点割点概念流程代码求无向图的割边桥理解代码强连通分量缩点大致流程代码例题Tarjan求LCA关于LCA本人博客讲解例题双连通分量点双连通图边双连通图对于一个连通图如果任意两点至少存在两条点不重复路径则称这个图为点双连通的简称双连通如果任意两点至少存在两条边不重复路径则称该图为边双连通的。点双连通图的定义等价于任意两条边都同在一个简单环中而边双连通图的定义等价于任意一条边至少在一个简单环中。对一个无向图点双连通的极大子图称为点双连通分量简称双连通分量边双连通的极大子图称为边双连通分量。强连通分量
我粗略提一下里面的参量 dfn[]表示该节点在DFS的过程中第一次搜索到的次序也就是第几个遍历到的点 low[]一开始和dfn[]相等但在回溯过程中不断维护最终成为这个强连通分量中dfn的最低值 节点u是某个强连通分量的根等价于dfn[u]和low[u]相等
代码
void Tarjan(int u)
{vis[u]1;low[u]dfn[u]cnt;for(int i0;imp[u].size();i){int vmp[u][i];if(dfn[v]0){Tarjan(v);//如果这个点还没访问过从这点继续开始找 low[x] min(low[x],low[v]);}if(vis[v]1)low[u]min(low[u],dfn[v]);//更新时间戳 }if(dfn[u]low[u]){sig;}
}题目
tarjan求割点
割点概念
割点无向连通图中去掉一个顶点及和它相邻的所有边图中的连通分量数增加则该顶点成为割点 求割点可以不用栈结构
流程
对于根节点如果有两个以上的子树就说明是割点因为取出后子树就会分离 对于非根节点对于边(u,v)如果low[v]dfn[u]此时u就是割点 tarjan(u,r) u:表示当前点 r表示的是树的root 所以r不变变的是u
代码
child用来统计孩子数目 cut[x]:表示x是否为割点
// u:当前点 r本次搜索树的root
void tarjan(ll u, ll r) {dfn[u] low[u] deep;ll child 0;for (unsigned i 0; i g[u].size(); i) {ll v g[u][i];if (!dfn[v]) {tarjan(v, r);low[u] min(low[u], low[v]);if (low[v] dfn[u] u ! r)cut[u] 1;//不是根而且他的孩子无法跨越他回到祖先if (r u)child; //如果是搜索树的根统计孩子数目}low[u] min(low[u], dfn[v]);//已经搜索过了}if (child 2 u r)//如果根节点的子树数量大于等于2 ,将根节点去掉之后两颗子树就分离了cut[r] 1;
}
求无向图的割边桥
理解
割边:在一个无向图中,去掉一条边(u, v),可以使图的连通分量增多的边, 就是割边,也称做桥
原理利用tarjan算法, 对于一条边的起点u,终点v,如果满足条件 low[v] dfn[u], 那么(u, v)就是一条割边, 因为这意味着不存在其他的边使得v可以回到u, 那么割掉就使图分离了. 需要注意的是跟割点不同, 没有等于号, 否则说明存在其他边回到起点, 那么就不是割边。 tarjan(int u,int pre)//pre表示u的父亲节点
代码
代码选自Network POJ-3694的题解 if(!dfn[v]){Tarjan(v, u);low[u] min(low[u], low[v]);if(low[v]dfn[u]) //isbridge[v]表示在树中以v为儿子结点的边是否为桥{isbridge[v] 1;sum_bridge;//桥的数量加一} }elselow[u] min(low[u], dfn[v]);强连通分量缩点
缩点的作用 1.可以把一个有向带环图变成一个有向无环图DAG因为我们把环给缩成一个集体这样我们就可以直接当做无环图做就可以 2.可以算缩点后每个点的出度 图来自
大致流程
在用Tarjan求完强连通分量后可以用一个数组color进行标记将同一个连通分量的点标记为相同数值这样再遍历一遍所有边之后如果有个边u-v的两侧不是一个数值说明不再一个连通分量则就从u所在颜色向v所在颜色生成一个边也就是u所在的连通分量向v所在的连通分量生成一条边最后这些新生成的边就是组成新的图就是缩点后的图。。 我们可以在此基础上计算缩点后的出入度
代码
const int MAXN 5e3 20;
const int MAXM 1e6 10;
int head[MAXN], cnt, tot, dfn[MAXN], low[MAXN], color[MAXN], col;
bool vis[MAXN];
int degree[MAXN];
stackint stc;
int n, m;
struct Edge {int to, next, dis;
}edge[MAXM 1];
void add_edge(int u, int v, int dis) {edge[cnt].to v;edge[cnt].next head[u];head[u] cnt;
}
void Tarjan(int x) {vis[x] 1;dfn[x] low[x] tot;stc.push(x);for(int i head[x]; i; i edge[i].next) {int to edge[i].to;if (!dfn[to]) {Tarjan(to);low[x] min(low[x], low[to]);} else if( vis[to] ) {low[x] min(low[x], dfn[to]);}}//以上为正常的tarjan求强连通分量 if(dfn[x] low[x]) {col ;while(true) {int top stc.top();//栈中最上面的点 stc.pop();color[top] col; //给同一连通分量的点上相同的颜色相当于缩点 vis[top] 0;// cout top ;if(top x) break; //遍历完后退出 }//cout endl;}
}
void solve(){for(int i 1; i n; i) {if(!dfn[i])Tarjan(i);}for(int x 1; x n; x) { //遍历 n个节点 for(int i head[x]; i; i edge[i].next) { //缩点后 每个点的出度 int to edge[i].to;if(color[x] ! color[to]) {degree[color[x]] ;//计算出度 }}}
}
void init () {cnt 1;tot 0;col 0;memset(vis, 0, sizeof(vis));memset(head, 0, sizeof(head));memset(dfn, 0, sizeof(dfn));memset(low, 0, sizeof(low));memset(degree, 0, sizeof(degree));memset(color, 0, sizeof(color));while(!stc.empty()) stc.pop();
}
int main () {std::ios::sync_with_stdio(false);cin.tie(0);while(cin n n) {cin m;init();int x, y;for(int i 1; i m; i) {cin x y;add_edge(x, y, 0);}solve();} return 0;
}例题
The Bottom of a Graph Poj 2553
Tarjan求LCA
关于LCA本人博客讲解
例题
Network POJ-3694
双连通分量
点双连通图
若一个无向连通图不存在割点则称它为“点双连通图”。
边双连通图
若一个无向连通图不存在割边则称它为“边双连通图”。
