ACM模板——强连通分量

Love The Way You Lie 2023-06-01 08:55 148阅读 0赞

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 vector<int> G[maxn];
     2 vector<int> rG[maxn];
     3 vector<int> vs;
     4 vector<int> ans[maxn];
     5 bool used[maxn];
     6 int V,E;
     7 int rnt = 0;
     8 void add_edge(int from,int to)
     9 {
    10     G[from].pb(to);
    11     rG[to].pb(from);
    12 }
    13 void dfs(int v)
    14 {
    15     used[v] = true;
    16     _for(i,0,G[v].size())
    17         if(!used[G[v][i]])
    18             dfs(G[v][i]);
    19     vs.pb(v);
    20 }
    21 void rdfs(int v,int k)
    22 {
    23     used[v] = true;
    24     ans[k].pb(v);
    25     _for(i,0,rG[v].size())
    26         if(!used[rG[v][i]])
    27             rdfs(rG[v][i],k);
    28 }
    29 //第k个集合里有哪些节点 ans[k]
    30 //rnt为最大集合的集合大小
    31 void Kosaraju()
    32 {
    33     memset(used,0,sizeof(used));
    34     _for(v,1,V+1)
    35         if(!used[v])
    36             dfs(v);
    37     
    38     memset(used,0,sizeof(used));
    39     int k = 0;
    40     _rep(i,vs.size()-1,-1)
    41         if(!used[vs[i]])
    42         {
    43             rdfs(vs[i],k);
    44             rnt = max(rnt,(int)ans[k].size());
    45             k ++;
    46         }
    47 }

Kosaraju

转载于:https://www.cnblogs.com/Asurudo/p/11536005.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/dae16677f5054cc0b1571966f0faedb6.png

发表评论取消回复

表情：

评论列表（有 0 条评论，148人围观）

还没有评论，来说两句吧...

相关阅读

相关 ACM模板——强连通分量

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] 1 vector<int> G[maxn]; 2

Love The Way You Lie/ 2023年06月01日 08:55/ 0 赞/ 149 阅读

相关【算法与数据结构】——强连通分量

强连通分量在一个有向图中，选取一个点集S，如果对于S中的任意两点u,v都满足u可到达v，则称S是强连通的。如果一个强连通点集S中，不能在加入更多的点使得它仍然强连通

阳光穿透心脏的1/2处/ 2022年10月14日 08:41/ 0 赞/ 201 阅读

相关迷宫城堡（强连通分量）

迷宫城堡 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Othe

￡神魔★判官ぃ/ 2022年08月02日 05:55/ 0 赞/ 195 阅读

相关浅谈双连通分量、强连通分量

初谈这个话题相信每一位都会感到一丝疑惑，主要原因是这个词中“分量”一词，当然，如果仅是为了了解和使用这两个术语，就不必在意这个无关大体的词语。好了，该谈谈正

桃扇骨/ 2022年07月14日 15:50/ 0 赞/ 241 阅读

相关浅谈双连通分量、强连通分量

初谈这个话题相信每一位都会感到一丝疑惑，主要原因是这个词中“分量”一词，当然，如果仅是为了了解和使用这两个术语，就不必在意这个无关大体的词语。好了，该谈谈

柔情只为你懂/ 2022年06月09日 23:27/ 0 赞/ 296 阅读

相关图论：连通分量和强连通分量

1.连通图 1.1 顶点的连通性在无向图G中，若从顶点vi到顶点vj有路径(当然从vj到vi也一定有路径)，则称vi和vj是连通的。 1.2 连通图在无向图G中，若

小鱼儿/ 2022年05月23日 10:27/ 0 赞/ 373 阅读

相关 Popular Cows POJ - 2186 (强连通分量)

Every cow's dream is to become the most popular cow in the herd. In a herd of N (1 <= N

Bertha 。/ 2022年02月17日 04:26/ 0 赞/ 273 阅读

相关求强连通分量-korasaju算法

基本思路两次dfs，第一次逆序，第二次计算连通分量的类别。待完善。 include<bits/stdc++.h> using namespace st

Love The Way You Lie/ 2021年11月10日 02:16/ 0 赞/ 331 阅读

相关 HDU11269 迷宫城堡(强连通分量)

迷宫城堡 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Othe

亦凉/ 2021年11月01日 05:32/ 0 赞/ 329 阅读

相关图之强连通、强连通图、强连通分量 Tarjan算法

一、解释在有向图G中，如果两个顶点间至少存在一条互相可达路径，称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连

秒速五厘米/ 2021年09月14日 03:12/ 0 赞/ 594 阅读