建设网站坂田,杭州网络推广运营公司,北京12345微信公众号,湖南城乡建设厅网站求强联通分量有很多种。 《C信息学奥赛一本通》 中讲过一个dfs求强联通分量的算法Kosdaraju#xff0c;为了骗字数我就待会简单的说说。然而我们这篇文章的主体是Tarjan#xff0c;所以我肯定说完之后再赞扬一下Tarjan大法好是不是 首先我们讲一下强联通分量 强联通分量指的… 求强联通分量有很多种。 《C信息学奥赛一本通》 中讲过一个dfs求强联通分量的算法Kosdaraju为了骗字数我就待会简单的说说。然而我们这篇文章的主体是Tarjan所以我肯定说完之后再赞扬一下Tarjan大法好是不是 首先我们讲一下强联通分量 强联通分量指的是图的一个子图。在这个子图中任意两个节点都可以互相到达。从定义上我们就可以看出是一个有向图来因为任意一个无向图都符合该定义。 而它的标准定义是有向图中任意两点都联通的最大子图。 咳咳首先庆祝一下哈——本人博客的第一张图。绘图历时3分钟。 在咱们举的例子中可以看出1 、2 、3 、5 通过边可以相互到达它们算一个强联通分量但4却被它们隔绝在外。从图中可以看出从4点出发不能到达任意一个点。所以它单个节点也算一个强联通分量。所以图中的强联通分量有两个一个是1-2-3-5一个是4。 ok看完了强联通分量是什么我们就讲一下Kosaraju。 这个算法的思路是对图进行DFS并记录每个点的退出顺序。再构造反图(就是有向边的方向全都反过来),按照退出顺序的逆序DFS反图对得到的点进行染色即为强联通分量。 讲完思路开始模拟。以起点1为起点遍历顺序如下 [ 1 2 3 5 4 5 3 2 4 4 1 ] 加粗斜体外带下划线的部分就是本图的退出顺序。 于是我们得到这样一个数组[ 5 3 2 4 1 ] 。按照这个数组的逆序对反图遍历得到 [ 5 3 2 1 退出 4 退出 ] 即得到要求的两个强联通分量。 还要两遍DFS麻烦的一比。看我大Tarjan一遍DFS就能求出强联通分量 首先我们要明确Tarjan要用到的两个数组dfn[] 和 low[] dfn指的是在DFS过程中访问到该点的顺序。从1开始DFS全图那么1的dfn值就是12的dfn值是2,5的dfn值是44的dfn值是5。剩下的一个类推 那么low呢low指的是如果逆着DFS序往前回溯该节点最早是由哪个节点走过来的。 比如在上图中2 、3 、5 、4 最早都是由1走过来的所以它们的low值都是1 下面贴出dfn和low的算法 每次dfs(点u){ dfn[u] 进入 dfs() 函数的次数 自己定义一个时间戳记录 如 time 枚举与其相邻的点v{ 如果 没有 访问过点v { ( 就是dfs树上的树边 ) dfs(v); 如果 v 能追溯 到 比“u 追溯到的最早的点” 更早的点 那么 u 就能 通过 v 来追溯到 那个点 low[u]min(low[u],low[v]); } 如果 访问过点v v在栈中 low[u]min(low[u],dfn[v]); } 缩点 } 上面那些伪代码是从伟大的GeneralLiu那里带过来的在此先%%% 然后 假设我们走到一个节点i发现这个i不能继续扩展了也就是dfn[i]low[i] 于是我们开始往回走。往回走的过程中我们就把和它一个分量的节点进行染色给它们统一的标记。 最后统计有多少种不同的标记即是强联通分量个数 luogu的一道题刻录光盘非常好可以用于练手。 放代码 #includeiostream
#includecstring
using namespace std;
int head[10000],num;
struct Edge{int next,to;
}edge[100000];
int stack[10000],top;
int color[10000],cnt;
int dfn[10000],low[10000];
int ID;
bool jd[10000];
int vis[10000];
inline void add(int from,int to){edge[num]{head[from],to};head[from]num;
}void tarjan(int x){dfn[x]ID;low[x]ID;jd[x]1;stack[top]x;for(int ihead[x];i;iedge[i].next){int toedge[i].to;if(!dfn[to]){tarjan(to);low[x]min(low[x],low[to]);}else if(jd[to]) low[x]min(low[x],dfn[to]);}if(dfn[x]low[x]){jd[x]0;color[x]cnt;while(stack[top]!x){color[stack[top--]]cnt;jd[stack[top1]]0;color[stack[top1]]cnt;}top--;}}int main(){int n;cinn;int x;for(int i1;in;i){while(cinxx!0){add(i,x);}}for(int i1;in;i){if(!dfn[i]) tarjan(i);}memset(jd,0,sizeof(jd));for(int i1;in;i){for(int jhead[i];j;jedge[j].next){if(color[i]!color[edge[j].to]){jd[color[edge[j].to]]1;}}}int ans0;for(int i1;icnt;i) if(!jd[i]) ans;coutansendl;return 0;
} 转载于:https://www.cnblogs.com/cellular-automaton/p/6895397.html
