通信工程毕设可以做网站吗,网页传奇游戏怎么注销,扬州工程造价信息网,免费手机网页强联通分量 强连通#xff1a;有向图 \(G\) 强连通表示#xff0c;\(G\) 中任意两个结点连通。 强连通分量( Strongly Connected Components #xff0c;简称 \(\operatorname{SCC}\) )#xff1a;极大的 强连通子图。 Tarjan 维护了以下两个变量#xff1a; \(dfn\) 有向图 \(G\) 强连通表示\(G\) 中任意两个结点连通。 强连通分量( Strongly Connected Components 简称 \(\operatorname{SCC}\) )极大的 强连通子图。 Tarjan 维护了以下两个变量 \(dfn\) 深度优先搜索遍历时结点 \(u\) 被搜索的次序 。 \(low\) 设以 \(u\) 为根的子树为 \(subtree(u)\) 。 \(low\) 定义为以下结点的 \(dfn\) 的最小值 \(subtree(u)\) 中的结点从 \(subtree(u)\) 通过 一条 不在搜索树上的边能到达的结点 。 从根开始的一条路径上的 \(dfn\) 严格递增\(low\) 严格非降。 对于一个连通分量图我们很容易想到在该连通图中有且仅有一个 \(dfn[u]low[u]\) 。该结点一定是在深度遍历的过程中该连通分量中第一个被访问过的结点因为它的 \(dfn\) 值和 \(low\) 值最小不会被该连通分量中的其他结点所影响。 因此在回溯的过程中判定 \(dfn[u]low[u]\) 的条件是否成立如果成立则栈中从 后面的结点构成一个 \(\operatorname{SCC}\) 。 P2341 [HAOI2006]受欢迎的牛 G \(-\) 模板 $\texttt{code}$ #define Maxn 10005
#define Maxm 50005
void tarjan(int u)
{dfn[u]low[u]Time; s.push(u),ins[u]true;for(int ihea[u];i;inex[i]){if(!dfn[ver[i]]) tarjan(ver[i]),low[u]min(low[ver[i]],low[u]);else if(ins[ver[i]]) low[u]min(dfn[ver[i]],low[u]);}if(dfn[u]low[u]){sum1;do{belong[u]sum;us.top(); s.pop(); ins[u]false;cnt[sum]1;} while(dfn[u]!low[u]);}
}for(int i1;in;i) if(!dfn[i]) tarjan(i); 时间复杂度 \(O(nm)\) 。 Kosaraju 复杂度 \(O(nm)\) 。 Garbow 复杂度 \(O(nm)\) 。 我们可以利用强联通分量将一张图的每个强连通分量都缩成一个点。 然后这张图会变成一个 \(\operatorname{DAG}\)可以进行拓扑排序以及更多其他操作 。 应用 \(-\) 缩点 P3387 【模板】缩点 for(int i1;in;i) if(!dfn[i]) tarjan(i);
for(int i1;itot[0];i)if(belong[fro[0][i]]!belong[ver[0][i]])add(1,belong[fro[0][i]],belong[ver[0][i]]),ind[belong[ver[0][i]]];
topo(); 割点与桥 在无向图中删去这个点 \(/\) 边会使极大强联通增大那么这个点 \(/\) 边为割点 \(/\) 桥 。 注意这里的 \(dfn\) 表示不经过父亲能到达的最小的 \(dfn\) 。 割点 P3388 【模板】割点(割顶) 关键条件 若 \(u\) 是根节点当至少存在 \(2\) 条边满足 \(low[v] dfn[u]\) 则 \(u\) 是割点 。 若 \(u\) 不是根节点当至少存在 \(1\) 条边满足 \(low[v] dfn[u]\) 则 \(u\) 是割点 。 $\texttt{code}$ void tarjan(int u,int fa)
{dfn[u]low[u]Time;for(int ihea[u];i;inex[i]){if(!dfn[ver[i]]){tarjan(ver[i],u),low[u]min(low[ver[i]],low[u]);if(low[ver[i]]dfn[u]) cnt[u]1;}else if(ver[i]!fa) low[u]min(dfn[ver[i]],low[u]);}
}for(int i1;in;i) if(!dfn[i]) cnt[i]-1,tarjan(i,0);
for(int i1;in;i) if(cnt[i]1) ans1; 割边(桥) 关键条件 当存在一条边条边满足 \(low[v] dfn[u]\) 则边 \(i\) 是割边 关键部分的代码 注意记录上一个访问的边时要记录边的编号不能记录上一个过来的节点(因为会有重边) $\texttt{code}$ void tarjan(int x,int Last_edg)
{dfn[x]low[x]Time;for(int ihea[x];i;inex[i]){if(!dfn[ver[i]]){tarjan(ver[i],i);low[x]min(low[x],low[ver[i]]);if(low[ver[i]]dfn[x]) edg[i]edg[i^1]1;}else if(i!(Last_edg^1)) low[x]min(low[x],dfn[ver[i]]);}
}for(int i1;in;i) if(!dfn[i]) tarjan(i,0);
for(int j2;jtot;j2) anstag[j]; 双联通分量 边双联通分量 显然找出每一个桥去掉这些桥之后的每一个联通块都是一个边双联通字图。 注意用边双缩点的时候先处理出割边之后用 \(\text{dfs}\) 求出每一个双联通分量不用栈 例题P2860 [USACO06JAN]Redundant Paths G $\texttt{solution}$ 一句话题意要将原图转化为边双联通图需要添加的最少边数 我们可以先将所有的桥找出来并同时对所有边双缩点会得到一颗缩完点的、由桥构成的“树”。 我们发现这棵“树”上“叶子结点”的个数除二向上取整就是需要添加的边的条数。 点双连通分量 小粉兔的圆方树——点双详解 【模板】点双连通分量 回忆 \(low\) 的定义就是 \(x\) 的子树内最多经过一条反祖边或一条向父亲的边能够到达的最小的 \(dfn\) 值。 当 \(x\) 不是这个连通块的根时如果存在一条边满足 \(low(ver)\ge dfn(x)\)那么 \(x\) 就是一个个点。 而 \(x\) 是根时\(x\) 需要存在至少两条边满足以上条件。 这是因为当 \(x\) 为根时没有父亲与之相连。 那么当我们在求点双时只需要判断子树内的 \(low\) 是否会 \(dfn(x)\)若会则说明子树中的点能够到达 \(x\) 的祖先\(x\) 必然不是个点。而若不会即 \(low(ver)\ge dfn(x)\)则说明 \(x\) 是这个点双的顶端个点这时可以将递归进入的点都弹出直至栈顶元素变为 \(ver\)再将 \(ver\) 从栈中弹出加上 \(x\) 就是这个点双联通分量了。 还要注意孤立点的情况。 如果需要处理点双中点的个数那么可以在栈中存放点例如一下代码 void tarjan(int x)
{dfn[x]low[x]Time,sta[tp]x;if(tp1 !hea[x]) { SCC[sum].pb(x); return; }for(int ihea[x];i;inex[i]){if(!dfn[ver[i]]){tarjan(ver[i]);low[x]min(low[x],low[ver[i]]);if(low[ver[i]]dfn[x]){sum;do { SCC[sum].pb(sta[tp--]); }while(sta[tp1]!ver[i]);SCC[sum].pb(x);}}else low[x]min(low[x],dfn[ver[i]]);}
} 而如果需要处理点双中的边那么就需要在栈中存边如以下代码 void tarjan(int x,int fa)
{dfn[x]low[x]Time;int cntson0;for(int ihea[x];i;inex[i]){if(!dfn[ver[i]]){sta[tp]i,tarjan(ver[i],i),cntson;low[x]min(low[x],low[ver[i]]);if(low[ver[i]]dfn[x]){isdian[x]true,sum;int tmp0;do{tmpsta[tp--];scc[sum].pb(fro[tmp]);scc[sum].pb(ver[tmp]);}while(tmp!i);}}else if(i!(fa^1)) low[x]min(low[x],dfn[ver[i]]); }if(fa0 cntson1) isdian[x]false;
}
