最恶心的一集具体题目见洛谷强连通分量基础题什么是强连通分量想象一张图就假设我要从北京到上海吧我们坐着高铁经过了n个城市到了上海在上海玩了几天后我们又坐着高铁走了另一条路没有经过上一次的一个城市重新回到了北京这样我们就构造了一个强连通分量。我们可以从u到v也可以从v到u。这就是一个强连通分量。但这个强连通分量必须是有向图。Tarjan算法是如何解决的当我们使用Tarjan时会用到一个栈来存储。我们每走一步就会把一个数放入并标记。low是用来记住自己的老大的dfn则为这个数本身的名字。所以每遇到一个新节点就会带他认识自己的老大并赐一个名字。下一步我们从这个点出发看看能走几条路继续深搜。当搜到了一个已经被访问过并且还在栈中就会判断谁是最小的谁就是老大。当遍历完后发现了一个low和dfn相等的数那么这就是root是老大。于是我们把这一个黑帮团队取一个名字并把老大的小弟们都找出来。注意一个团体可能只有老大一个人。在实现代码时我们要每一个点都遍历一遍。已经是老大或小弟的除外。输出时记得把输出过的标记一下。以防重复输出。AC代码自行参考阅读文章时使用代码理解风味更佳~#includebits/stdc.husingnamespacestd;constintN1e45;intn,m,u,v;intcnt,s,c;intstk[N],in_stk[N];intlow[N],dfn[N];vectorintg[N];intflag[N];intans_flag[N];voidTarjan(intnum){cnt;low[num]cnt;dfn[num]cnt;s;stk[s]num;in_stk[num]1;for(inti0;ig[num].size();i){intvg[num][i];if(dfn[v]0){Tarjan(v);low[num]min(low[num],low[v]);}elseif(in_stk[v]1){low[num]min(low[num],dfn[v]);}}if(low[num]dfn[num]){c;while(1){intzstk[s];in_stk[z]0;s--;ans_flag[z]c;if(numz)break;}}return;}signedmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cinnm;for(inti1;im;i){cinuv;g[u].push_back(v);}for(inti1;in;i){if(dfn[i]0){Tarjan(i);}}coutc\n;for(inti1;in;i){if(flag[i]0){for(intj1;jn;j){if(ans_flag[j]ans_flag[i]){coutj ;flag[j]1;}}cout\n;}}return0;}点个赞吧QwQ球球了
C++图论4：Tarjan算法之强连通分量
最恶心的一集具体题目见洛谷强连通分量基础题什么是强连通分量想象一张图就假设我要从北京到上海吧我们坐着高铁经过了n个城市到了上海在上海玩了几天后我们又坐着高铁走了另一条路没有经过上一次的一个城市重新回到了北京这样我们就构造了一个强连通分量。我们可以从u到v也可以从v到u。这就是一个强连通分量。但这个强连通分量必须是有向图。Tarjan算法是如何解决的当我们使用Tarjan时会用到一个栈来存储。我们每走一步就会把一个数放入并标记。low是用来记住自己的老大的dfn则为这个数本身的名字。所以每遇到一个新节点就会带他认识自己的老大并赐一个名字。下一步我们从这个点出发看看能走几条路继续深搜。当搜到了一个已经被访问过并且还在栈中就会判断谁是最小的谁就是老大。当遍历完后发现了一个low和dfn相等的数那么这就是root是老大。于是我们把这一个黑帮团队取一个名字并把老大的小弟们都找出来。注意一个团体可能只有老大一个人。在实现代码时我们要每一个点都遍历一遍。已经是老大或小弟的除外。输出时记得把输出过的标记一下。以防重复输出。AC代码自行参考阅读文章时使用代码理解风味更佳~#includebits/stdc.husingnamespacestd;constintN1e45;intn,m,u,v;intcnt,s,c;intstk[N],in_stk[N];intlow[N],dfn[N];vectorintg[N];intflag[N];intans_flag[N];voidTarjan(intnum){cnt;low[num]cnt;dfn[num]cnt;s;stk[s]num;in_stk[num]1;for(inti0;ig[num].size();i){intvg[num][i];if(dfn[v]0){Tarjan(v);low[num]min(low[num],low[v]);}elseif(in_stk[v]1){low[num]min(low[num],dfn[v]);}}if(low[num]dfn[num]){c;while(1){intzstk[s];in_stk[z]0;s--;ans_flag[z]c;if(numz)break;}}return;}signedmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cinnm;for(inti1;im;i){cinuv;g[u].push_back(v);}for(inti1;in;i){if(dfn[i]0){Tarjan(i);}}coutc\n;for(inti1;in;i){if(flag[i]0){for(intj1;jn;j){if(ans_flag[j]ans_flag[i]){coutj ;flag[j]1;}}cout\n;}}return0;}点个赞吧QwQ球球了