12388. 图论割边

快来打我* 2023-07-17 05:57 24阅读 0赞

# 12388. 图论割边 #

n个顶点m条边，请求割边

## 输入格式: ##

第一行给定三个整数 n，m 。n 个城镇，m 条道路(双向道路)。接下来给出 m 行，每行两个正整数表示这两个城镇之间有边相连。

## 输出格式: ##

一个整数，有几条关键道路。

样例 1 :

输入:  
6 6  
1 3  
1 4  
2 3  
2 4  
2 5  
5 6

输出:  
2

说明:  
2-5和5-6是桥

#include <cstdio>
    #include <vector>
    #include <cstring>
    
    
    using namespace std;
    
    
    const int max_n = 1e5 + 10;
    int n,m;
    int num[max_n],low[max_n];
    int time_index,a,b;
    vector<int> g[max_n];
    int ans;
    
    
    void dfs(int cur,int fa)
    {
        
        ++time_index;
        num[cur]=time_index;
        low[cur]=time_index;
    
        for(int i=0;i<g[cur].size();++i)
        {
        
            int v=g[cur][i];
            if(num[v]==0)
            {
        
                dfs(v,cur);
                low[cur]=min(low[cur],low[v]);
                if(low[v]>num[cur])
                {
        
                    ++ans;
                }
            }
            else if(fa!=v)
            {
        
                low[cur]=min(low[cur],num[v]);
            }
        }
    }
    
    void solve()
    {
        
        ans=0;
        time_index=0;
        memset(num,0,sizeof(num));
    
        dfs(1,1);
    
        printf("%d",ans);
    }
    
    
    int main()
    {
        
        scanf("%d %d",&n,&m);
        for(int i=0;i<m;++i)
        {
        
            scanf("%d %d",&a,&b);
            g[a].push_back(b);
            g[b].push_back(a);
        }
    
        solve();
    
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关图论

一、图的常用概念　　1、顶点（vertex）　　2、边（edge）　　3、路径　　4、无向图：顶点之间的连接没有方向　　![1007094-201909

柔光的暖阳◎/ 2023年10月10日 07:53/ 0 赞/ 188 阅读

相关 12388. 图论割边

12388. 图论割边 n个顶点m条边，请求割边输入格式: 第一行给定三个整数 n，m 。n 个城镇，m 条道路(双向道路)。接下来给出 m 行，每行两个正整数

快来打我*/ 2023年07月17日 05:57/ 0 赞/ 25 阅读

相关 12178. 破坏牛棚割点割边

1. 破坏牛棚约翰意识到贝茜建设网络花费了他巨额的经费，就把她解雇了。贝茜很愤怒，打算狠狠报复。她打算破坏刚建成的约翰的网络。约翰的网络是树形的，连接着N(1≤

爱被打了一巴掌/ 2023年07月17日 05:56/ 0 赞/ 132 阅读

相关 Caocao's Bridges （最小的割边）

目录 Caocao's Bridges （最小的割边）题目题意思路题解 Caocao's

╰+攻爆jí腚メ/ 2023年06月01日 06:11/ 0 赞/ 107 阅读

相关图的割点算法与图的割边算法

目录图的割点算法与图的割边算法割点思路割边图的割点算法与图的割边算法

深藏阁楼爱情的钟/ 2023年06月01日 06:11/ 0 赞/ 91 阅读

相关图论

http://[blog.csdn.net/pipisorry/article/details/52518118][blog.csdn.net_pipisorry_articl

清疚/ 2022年09月25日 15:21/ 0 赞/ 390 阅读

相关 ZOJ 2588-Burning Bridges（割边）

Burning Bridges -------------------- Time Limit: 5 Seconds Memory Limit: 32768 KB ---

墨蓝/ 2022年09月25日 11:20/ 0 赞/ 225 阅读

相关 tarjin算法割点割边

[Tarjan算法：求解图的割点与桥（割边）][Tarjan] void tarjan(int u, int root) {

绝地灬酷狼/ 2022年03月10日 06:27/ 0 赞/ 307 阅读

相关 UVA 11248 Frequency Hopping 求割边集

题意：给定一个有向网络，每条边均有一个容量。问是否存在一个从点1到点N，流量为C的流，如果不存在，是否可以恰好修改一条弧的容量，使得存在这样的流。思路：网络流板子题，

我会带着你远行/ 2022年01月22日 14:47/ 0 赞/ 264 阅读

相关 hdu 4738 Caocao's Bridges(割边)

[题目链接][Link 1] 用tarjan求桥上的最小权值 include<bits/stdc++.h> define ll long long int

墨蓝/ 2021年12月03日 06:19/ 0 赞/ 308 阅读