强连通分量 void tarjan(int u){ vis[u]=true; LOW[u]=DFN[u]=cnt++; for(int v:g[u]){if(!DFN[v]){//没访问过继续tarjan(v);LOW[u]=min(LOW[u],LOW[v]);}else if(vis[v])//还在栈中更新LOW[u]=min(LOW[u],DFN[v]); } ans+=DFN[u]==LOW[u]; }缩点 void tarjan(int u){ vis[u]=true; LOW[u]=DFN[u]=cnt++; Q.push(u);//入栈 for(int v:g[u]){if(!DFN[v]){//没访问过继续tarjan(v);LOW[u]=min(LOW[u],LOW[v]);}else if(vis[v])//还在...
<style></style>从这里开始预备知识 两个数组 Tarjan 算法的应用求割点和割边 求点-双连通分量 求边-双连通分量 求强连通分量预备知识设无向图$G_{0} = (V_{0}, E_{0})$，其中$V_{0}$为定点集合，$E_{0}$为边集，设有向图$G_{1} = (V_{1}, E_{1})$，其中$V_{1}$为定点集合，$E_{1}$为边集。无向图中的路径：如果存在一个顶点序列$v_{p},v_{i_{1}},\cdots,v_{i_{k}},v_{q}$，使得$\left ( v_{p}, v_{i_{1}} \right ),\left ( v_{i_{...
概念：在有向图G中，如果两个定点u可以到达v，并且v也可以到达u，那么我们称这两个定点强连通。 如果有向图G的任意两个顶点都是强连通的，那么我们称G是一个强连通图。 一个有向图中的最大强连通子图，称为强连通分量。tarjan的主要思想： 从一个点开始DFS，记录两个数组，dfn[]和low[]。 其中，dfn[i]指的是到达第i个点的时间。 low[i]指第i个点直接或间接可到达的点中的最小dfn[j]。 low[i]数组的初始值为dfn[i]。 举个例子，如图...
求加最少的边使图为强连通图#include<cstdio> #include<cstring> #include<algorithm> #include<stack> #include<vector> using namespace std; const int maxn=20000+10; int n,m; vector<int> G[maxn]; stack<int> S; int dfs_clock,scc_cnt; int pre[maxn],low[maxn],sccno[maxn]; bool in0[maxn],out0[maxn]; void dfs(int u) {pre[u]=low[u]=++dfs_clock;S.push(u);for(int i=0;i<G[u].size();i++){int v=G[u][i];if(!pre[v])...
因为最近在学2sat，需要学习前置技能—Tarjan算法，所以花了一天的时间学习这个算法 算法步骤： 1.从一个点开始dfs，并加入栈 2.如果下一个点没有到过，跳到第一步 3.如果下一个点到过，并且在栈中，下一个点到这个点，这一段构成一个回路，也就是可以缩点 具体实现void dfs(int x) {st.push(x); //加入栈dis[x]=1; //x点在栈中dfn[x]=low[x]=++te; //dfn用来表示某个点访问过，并且记录初始的low值for(int i=f[x];...
本文转自：www.cnblogs.com/collectionne/p/6847240.html 供大家学习 前言：之前翻译过一篇英文的关于割点的文章（英文原文、翻译），但是自己还有一些不明白的地方，这里就再次整理了一下。有兴趣可以点我给的两个链接。 割点的概念 在无向连通图中，如果将其中一个点以及所有连接该点的边去掉，图就不再连通，那么这个点就叫做割点（cut vertex / articulation point）。 例如，在下图中，0、3是割点，因为将0和3中任意一...