梗概第一趴——有向图的连通性即强联通分量。强联通分量一个听起来就很高级的名字实则比它的名字还复杂还有堪比线段树的代码量(蚌埠住了)概念在有向图中 两个点强联通当且仅当任意一点都能直接或间接到达另外一点。如果一个有向图任意两点均强联通那么称该图为强连通图。强连通分量Strongly Connected ComponentsSCC是有向图中极大的强连通子图。这个概念有点意思极大?是多大极大就是最大。其实就是说一张图中不可能有两个相交的SCC否则它们都不满足“极大”要将它们合并才是真正的SCC。那这玩意儿有何作用呢那可太有用了。一个环可以视作一个SCC那么把一张图中所有SCC都变成一个个点那么它就会变成——有向无环图(D i r e c t e d A c y c l i c G r a p h D A G Directed\ Acyclic\ GraphDAGDirectedAcyclicGraphDAG)DAG就更有意思了配合拓扑序做个DP啊…………来来回回加起来就直接超过线段树。话不多说请出主角Tarjan(依旧久违翻译官正经名字叫塔扬不过当汉语拼音读他见好像也无伤大雅)罗伯特·塔扬R o b e r t T a r j a n Robert\ TarjanRobertTarjan美国计算机科学家普林斯顿大学教授。这罗教授T a r j a n TarjanTarjan教授可厉害拿过的奖一页放不下有好多好多算法都是以他命名的(包括但不限于求SCC,LCA)并查集、Splay、Toptree 也是他发明的。在学习罗教授的算法之前先来个前摇DFS生成树(叠甲以下内容严重抄袭OI Wiki有需要可直接移步)好久没放过图了先把图贴上来DFS生成树简单来说就是随便找一个点跑DFS不撞南墙不回头。一个图会有很多DFS生成树取决于DFS的起始点和顺序。其中DFS走过的边称为树边(T r e e E d g e Tree\ EdgeTreeEdge)即上图中黑色的边。但一张图中肯定不止有树边。反祖边B a c k E d g e Back\ EdgeBackEdge也称回边指在搜索过程中从某个结点指向其祖先结点的非树边即上图中红色的边。前向边F o r w a r d E d g e Forward\ EdgeForwardEdge)指在搜索过程中从某个结点指向其子树中后代结点的非树边即上图中绿色的边。横叉边C r o s s E d g e Cross\ EdgeCrossEdge指在搜索过程中从某个结点指向非祖先、非后代且已访问的结点的边即上图中蓝色的边。这玩意儿跟SCC有什么关系呢不难得到如果结点u uu是其所在SCC在生成树中的第一个结点那么它所在的SCC在以它为根的子树上u uu称为该SCC的根。证明见OI Wiki在T a r j a n TarjanTarjan算法中利用栈对图DFS并产生DFS生成树。期间需要维护两个变量d f n [ u ] dfn[u]dfn[u]表示结点u uu的DFS序即u uu被搜索到的次序。l o w [ u ] low[u]low[u]表示在u uu的子树中能够回溯到的最早的已经在栈中的结点的d f n dfndfn。这个点要么在子树上要么与子树通过一条非树边连接。在搜索过程中对于结点u uu和与其相邻的结点v vvv vv不是u uu的父节点考虑 3 种情况v vv未被访问那么搜索v vv将v vv入栈根据l o w lowlow的定义可以用l o w [ v ] low[v]low[v]更新l o w [ u ] low[u]low[u]v vv已被访问且在栈中那么用d f n [ v ] dfn[v]dfn[v]更新l o w [ u ] low[u]low[u]。注意在此情况中v vv与u uu通过一条非树边连接所以不能用l o w [ v ] low[v]low[v]更新l o w [ u ] low[u]low[u]v vv已被访问且不在栈中说明v vv已经在某个SCC中无需处理。容易想到在连通图中有且仅有一个u uu满足d f n [ u ] l o w [ u ] dfn[u]low[u]dfn[u]low[u]此时u uu就是该SCC的根。把栈中u uu上方结点全部推出即可得到该SCC。时间复杂度O ( n m ) O(nm)O(nm)猪脑已过载代码模版参见洛谷B3609#includebits/stdc.husingnamespacestd;#defineN100005vectorintg[N];intn,m,dfn[N],low[N];inttimer;//时间戳intsc;//SCC个数stackints;vectorintvec[N];//存每一个SCCboolins[N];//标记voidtarjan(intu){dfn[u]low[u]timer;s.push(u);ins[u]1;for(intv:g[u]){if(!dfn[v]){//情况1tarjan(v);low[u]min(low[u],low[v]);}elseif(ins[v])//情况2low[u]min(low[u],dfn[v]);}if(dfn[u]low[u]){sc;while(1){intvs.top();s.pop();ins[v]0;vec[sc].push_back(v);if(vu)break;}}}intmain(){cinnm;intu,v;while(m--){cinuv;g[u].push_back(v);}for(inti1;in;i){if(!dfn[i])tarjan(i);}for(inti1;isc;i)sort(vec[i].begin(),vec[i].end());sort(vec1,vec1sc);//排序coutscendl;for(inti1;isc;i){for(intj:vec[i])coutj ;coutendl;}return0;}51行的代码开开胃以后进入真正的应用——缩点模板参见洛谷P3387看着很简单小点变大点实际上也不难。遍历每条边如果边两端同属一个SCC就扔掉这条边否则建新边。好缩完点就开始做拓扑序。根据本题题意很明显是DP。状态d p [ u ] dp[u]dp[u]表示遍历到u uu这个大点获得的最大价值。转移对于所有指向u uu的大点v vvd p [ u ] m a x ( d p [ u ] , d p [ v ] v a l [ u ] ) dp[u]max(dp[u],dp[v]val[u])dp[u]max(dp[u],dp[v]val[u])。代码#includebits/stdc.husingnamespacestd;#defineN100005vectorintg[N],g2[N];intn,m,dfn[N],low[N],timer,sc,a[N],dp[N],val[N];intscc[N],into[N];//记录点在第几个SCC大点的入度intp[N],q[N];//记录边的两端点stackints;boolins[N];queueintqu;voidtarjan(intu){dfn[u]low[u]timer;s.push(u);ins[u]1;for(intv:g[u]){if(!dfn[v]){tarjan(v);low[u]min(low[u],low[v]);}elseif(ins[v])low[u]min(low[u],dfn[v]);}if(dfn[u]low[u]){sc;while(1){intvs.top();s.pop();ins[v]0;scc[v]sc;val[sc]a[v];if(vu)break;}}}inttopo(){intans0;for(inti1;isc;i){if(into[i]0){qu.push(i);dp[i]val[i];}}while(!qu.empty()){intuqu.front();qu.pop();ansmax(ans,dp[u]);for(intv:g2[u]){dp[v]max(dp[v],dp[u]val[v]);into[v]--;if(!into[v])qu.push(v);}}returnans;}signedmain(){cinnm;intu,v;for(inti1;in;i)cina[i];for(inti1;im;i){cinp[i]q[i];g[p[i]].push_back(q[i]);}for(inti1;in;i)if(!dfn[i])tarjan(i);for(inti1;im;i){intxscc[p[i]],yscc[q[i]];if(xy)continue;g2[x].push_back(y);into[y];}couttopo();return0;}代码量区区71行❌️—————————————————————— T h e E n d —————————————————————— ——————————————————————The\ \ End————————————————————————————————————————————TheEnd——————————————————————
算法总结：图论——连通图(一)
梗概第一趴——有向图的连通性即强联通分量。强联通分量一个听起来就很高级的名字实则比它的名字还复杂还有堪比线段树的代码量(蚌埠住了)概念在有向图中 两个点强联通当且仅当任意一点都能直接或间接到达另外一点。如果一个有向图任意两点均强联通那么称该图为强连通图。强连通分量Strongly Connected ComponentsSCC是有向图中极大的强连通子图。这个概念有点意思极大?是多大极大就是最大。其实就是说一张图中不可能有两个相交的SCC否则它们都不满足“极大”要将它们合并才是真正的SCC。那这玩意儿有何作用呢那可太有用了。一个环可以视作一个SCC那么把一张图中所有SCC都变成一个个点那么它就会变成——有向无环图(D i r e c t e d A c y c l i c G r a p h D A G Directed\ Acyclic\ GraphDAGDirectedAcyclicGraphDAG)DAG就更有意思了配合拓扑序做个DP啊…………来来回回加起来就直接超过线段树。话不多说请出主角Tarjan(依旧久违翻译官正经名字叫塔扬不过当汉语拼音读他见好像也无伤大雅)罗伯特·塔扬R o b e r t T a r j a n Robert\ TarjanRobertTarjan美国计算机科学家普林斯顿大学教授。这罗教授T a r j a n TarjanTarjan教授可厉害拿过的奖一页放不下有好多好多算法都是以他命名的(包括但不限于求SCC,LCA)并查集、Splay、Toptree 也是他发明的。在学习罗教授的算法之前先来个前摇DFS生成树(叠甲以下内容严重抄袭OI Wiki有需要可直接移步)好久没放过图了先把图贴上来DFS生成树简单来说就是随便找一个点跑DFS不撞南墙不回头。一个图会有很多DFS生成树取决于DFS的起始点和顺序。其中DFS走过的边称为树边(T r e e E d g e Tree\ EdgeTreeEdge)即上图中黑色的边。但一张图中肯定不止有树边。反祖边B a c k E d g e Back\ EdgeBackEdge也称回边指在搜索过程中从某个结点指向其祖先结点的非树边即上图中红色的边。前向边F o r w a r d E d g e Forward\ EdgeForwardEdge)指在搜索过程中从某个结点指向其子树中后代结点的非树边即上图中绿色的边。横叉边C r o s s E d g e Cross\ EdgeCrossEdge指在搜索过程中从某个结点指向非祖先、非后代且已访问的结点的边即上图中蓝色的边。这玩意儿跟SCC有什么关系呢不难得到如果结点u uu是其所在SCC在生成树中的第一个结点那么它所在的SCC在以它为根的子树上u uu称为该SCC的根。证明见OI Wiki在T a r j a n TarjanTarjan算法中利用栈对图DFS并产生DFS生成树。期间需要维护两个变量d f n [ u ] dfn[u]dfn[u]表示结点u uu的DFS序即u uu被搜索到的次序。l o w [ u ] low[u]low[u]表示在u uu的子树中能够回溯到的最早的已经在栈中的结点的d f n dfndfn。这个点要么在子树上要么与子树通过一条非树边连接。在搜索过程中对于结点u uu和与其相邻的结点v vvv vv不是u uu的父节点考虑 3 种情况v vv未被访问那么搜索v vv将v vv入栈根据l o w lowlow的定义可以用l o w [ v ] low[v]low[v]更新l o w [ u ] low[u]low[u]v vv已被访问且在栈中那么用d f n [ v ] dfn[v]dfn[v]更新l o w [ u ] low[u]low[u]。注意在此情况中v vv与u uu通过一条非树边连接所以不能用l o w [ v ] low[v]low[v]更新l o w [ u ] low[u]low[u]v vv已被访问且不在栈中说明v vv已经在某个SCC中无需处理。容易想到在连通图中有且仅有一个u uu满足d f n [ u ] l o w [ u ] dfn[u]low[u]dfn[u]low[u]此时u uu就是该SCC的根。把栈中u uu上方结点全部推出即可得到该SCC。时间复杂度O ( n m ) O(nm)O(nm)猪脑已过载代码模版参见洛谷B3609#includebits/stdc.husingnamespacestd;#defineN100005vectorintg[N];intn,m,dfn[N],low[N];inttimer;//时间戳intsc;//SCC个数stackints;vectorintvec[N];//存每一个SCCboolins[N];//标记voidtarjan(intu){dfn[u]low[u]timer;s.push(u);ins[u]1;for(intv:g[u]){if(!dfn[v]){//情况1tarjan(v);low[u]min(low[u],low[v]);}elseif(ins[v])//情况2low[u]min(low[u],dfn[v]);}if(dfn[u]low[u]){sc;while(1){intvs.top();s.pop();ins[v]0;vec[sc].push_back(v);if(vu)break;}}}intmain(){cinnm;intu,v;while(m--){cinuv;g[u].push_back(v);}for(inti1;in;i){if(!dfn[i])tarjan(i);}for(inti1;isc;i)sort(vec[i].begin(),vec[i].end());sort(vec1,vec1sc);//排序coutscendl;for(inti1;isc;i){for(intj:vec[i])coutj ;coutendl;}return0;}51行的代码开开胃以后进入真正的应用——缩点模板参见洛谷P3387看着很简单小点变大点实际上也不难。遍历每条边如果边两端同属一个SCC就扔掉这条边否则建新边。好缩完点就开始做拓扑序。根据本题题意很明显是DP。状态d p [ u ] dp[u]dp[u]表示遍历到u uu这个大点获得的最大价值。转移对于所有指向u uu的大点v vvd p [ u ] m a x ( d p [ u ] , d p [ v ] v a l [ u ] ) dp[u]max(dp[u],dp[v]val[u])dp[u]max(dp[u],dp[v]val[u])。代码#includebits/stdc.husingnamespacestd;#defineN100005vectorintg[N],g2[N];intn,m,dfn[N],low[N],timer,sc,a[N],dp[N],val[N];intscc[N],into[N];//记录点在第几个SCC大点的入度intp[N],q[N];//记录边的两端点stackints;boolins[N];queueintqu;voidtarjan(intu){dfn[u]low[u]timer;s.push(u);ins[u]1;for(intv:g[u]){if(!dfn[v]){tarjan(v);low[u]min(low[u],low[v]);}elseif(ins[v])low[u]min(low[u],dfn[v]);}if(dfn[u]low[u]){sc;while(1){intvs.top();s.pop();ins[v]0;scc[v]sc;val[sc]a[v];if(vu)break;}}}inttopo(){intans0;for(inti1;isc;i){if(into[i]0){qu.push(i);dp[i]val[i];}}while(!qu.empty()){intuqu.front();qu.pop();ansmax(ans,dp[u]);for(intv:g2[u]){dp[v]max(dp[v],dp[u]val[v]);into[v]--;if(!into[v])qu.push(v);}}returnans;}signedmain(){cinnm;intu,v;for(inti1;in;i)cina[i];for(inti1;im;i){cinp[i]q[i];g[p[i]].push_back(q[i]);}for(inti1;in;i)if(!dfn[i])tarjan(i);for(inti1;im;i){intxscc[p[i]],yscc[q[i]];if(xy)continue;g2[x].push_back(y);into[y];}couttopo();return0;}代码量区区71行❌️—————————————————————— T h e E n d —————————————————————— ——————————————————————The\ \ End————————————————————————————————————————————TheEnd——————————————————————
