首页 > 其他分享 >图论-割边与边双连通分量

图论-割边与边双连通分量

时间:2024-05-22 18:59:36浏览次数:16  
标签:图论 连通 int 割边 back dfn cnt isbri

首先是两篇模板

割边

点击查看代码
int head[N], cnt = 1;
struct Edge{
    int from, to, nxt;
}e[N << 1];
void add(int u, int v){
    e[++cnt].from = u;
    e[cnt].to = v;
    e[cnt].nxt = head[u];
    head[u] = cnt;
}

int dfn[N], back[N], tim, bri_cnt; // dfn[i] 时间戳  back[i] 回退到祖先
bool isbri[N << 1]; // 结果数组

void dfs(int u, int in_edg){ // 和求割点作用相同,相当于传了个 fa
    dfn[u] = back[u] = ++tim;
    for(int i = head[u]; i != 0; i = e[i].nxt){
        int v = e[i].to;
        if(!dfn[v]){
            dfs(v, i);
            back[u] = min(back[u], back[v]);
            if(back[v] > dfn[u]){ // >= 变成 > 就是割边了
                isbri[i] = isbri[i^1] = true;
                bri_cnt++;
            }
        }
        else if(i != (in_edg^1)){ // 这回关系大了,因为判断条件少了等于
            back[u] = min(back[u], dfn[v]); // 注意不是  back[v]
        }
    }
}

边双连通分量

点击查看代码
int head[N], cnt = 1;
struct Edge{
    int from, to, nxt;
}e[N << 1];
void add(int u, int v){
    e[++cnt].from = u;
    e[cnt].to = v;
    e[cnt].nxt = head[u];
    head[u] = cnt;
}

int dfn[N], back[N], tim, bri_cnt, dcc_cnt; // dfn[i] 时间戳  back[i] 回退到祖先
bool isbri[N << 1]; // 结果数组
stack<int> stk;
vector<int> dcc[N];

void dfs(int u, int in_edg){ // 和求割点作用相同,相当于传了个 fa
    dfn[u] = back[u] = ++tim;
    for(int i = head[u]; i != 0; i = e[i].nxt){
        int v = e[i].to;
        if(!dfn[v]){
            dfs(v, i);
            back[u] = min(back[u], back[v]);
            if(back[v] > dfn[u]){ // >= 变成 > 就是割边了
                isbri[i] = isbri[i^1] = true;
                bri_cnt++;
            }
        }
        else if(i != (in_edg^1)){ // 这回关系大了,因为判断条件少了等于
            back[u] = min(back[u], dfn[v]); // 注意不是  back[v]
        }
    }
    if(dfn[u] == back[u]){
        ++dcc_cnt;
        while(1){
            int y = stk.top(); stk.pop();
            dcc[dcc_cnt].push_back(y);
            if(y == u) break;
        }
    }
}

标签:图论,连通,int,割边,back,dfn,cnt,isbri
From: https://www.cnblogs.com/9102qyy/p/18206903

相关文章

  • 图论-割点与点双连通分量
    首先是两篇的代码割点点击查看代码inthead[N],cnt=0;structEdge{intfrom,to,nxt;}e[N<<1];voidadd(intu,intv){e[++cnt].from=u;e[cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;}intdfn[N],back[N],tim;//dfn[i]时......
  • 关于 图论建模 的一些技巧
    分层图思想分层图在最短路中经常用到。直观上讲,就是将一个图复制k倍,互相是平行的,即互不影响,分层图两两之间会有决策边相连。这就等价于要在一个图上进行k次决策,对于每次决策,不影响图的结构,只影响目前的状态或代价。一般将决策前的状态和决策后的状态之间连接一条权值......
  • 解锁服务器连接状态新姿势:tcping工具助你高效诊断网络连通性
    使用tcping工具检测服务器连接状态在IT运维环境中,由于安全考虑,很多服务器和交换机可能会禁用ICMP(InternetControlMessageProtocol)响应,即“ping”请求,以防止ICMPFLOOD攻击和不必要的资源消耗。然而,运维人员仍需要一种方法来验证与这些服务器的连接状态。在这种情况下,tcping......
  • 【图的连通性】【并查集】【拓扑排序】
    在图论中,不同类型的图(无向图和有向图)需要使用不同的算法和数据结构来处理它们的特性和问题。这里我们将讨论如何使用并查集来解决无向图的连通性问题,以及如何使用深度优先搜索(DFS)、广度优先搜索(BFS)和拓扑排序来解决有向图中的依赖性问题。无向图的连通性:并查集对于无向图的连通......
  • 图论-割点与割边
    这是摘自算法书上的一篇Tarjan求割点算法dfn[i]代表时间戳数组back[i]代表该点不依靠祖先节点能回到的最远的祖先节点采用链式前向星建图,结果存储在iscut[]数组中点击查看代码inthead[N],cnt=0;structEdge{intfrom,to,nxt;}e[N<<1];voidadd(......
  • 24/05/08 图论
    \(\color{purple}(1)\)CF746GNewRoads构造一棵\(n\)个点的深度为\(t\)的树,以\(1\)为根,使其中深度为\(i\)的点有\(a_i\)个且叶节点有\(k\)个。或报告无解。\(t,k\len\le2\times10^5\)。为了方便,我们令根节点的深度为\(1\)。所有读入都向后顺延一位。......
  • 24/05/07 图论
    \(\color{green}(1)\)CF711DDirectedRoads有\(n\)个点和\(n\)条边,第\(i\)条边从\(i\)连到\(a_i\)(保证\(i\nea_i\))。每条边需要指定一个方向(无向边变为有向边)。问有多少种指定方向的方案使得图中不出现环,答案对\(10^9+7\)取模。\(n\le2\times10^5\)......
  • 【网络自动化运维】使用pythonping检查设备的连通性并记录可达设备(eNSP模拟器)
    实验拓扑:PC的IP地址和五台交换机的地址在同一网段,具体IP如图所示。现在保证直连网络能够通信,并且故意将SW5的接口shutdown掉,保证无法联通,作为对照的测试设备。在PC上运行python代码,测试与五台交换机的连通性。由于本次测试使用的是pythonping模块,这并不是python自带的模块,需要......
  • 好题——图论
    前言本文章将会持续更新,主要是一些个人觉得比较妙的题,主观性比较强(给自己记录用的),有讲错请补充。带!号的题是基础例题,带*号的是推荐首先完成的题(有一定启发性的)。图论最短路P1119灾后重建此题看到以后以为是很简单的最短路问题(实际也不难),就写了dijkstra,然后光荣的tie......
  • 24/04/27 图论及 dfs 序相关
    \(\color{green}(1)\)CF721CJourney给定一张\(n\)个点\(m\)条边的有向无环图,边有边权。构造一条\(1\ton\)的路径使得其边权和\(\lek\)且经过的点数最多。\(n,m\le5\times10^3\),\(k\le10^9\)。最简单的想法是设状态\(f_{i,j}\)表示\(1\toi\)的边权......