发布日期：2021-05-14 16:48:43 浏览次数：15 分类：精选文章

本文共 2524 字，大约阅读时间需要 8 分钟。


               
    图连通性检查                
                
     #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #define IL inline#define x first#define y secondtypedef long long ll;using namespace std;const int M = 4010;int n, m;int h[M], ne[M], idx, e[M];bool st[M];int u, v;void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++;}bool dfs(int u1) { if (u1 == v) return true; st[u1] = true; for (int i = h[u1]; ~i; i = ne[i]) { int j = e[i]; if (st[j]) continue; if (dfs(j)) return true; } return false;}int main() { cin >> n >> m; memset(h, -1, sizeof(h)); while (m--) { int a, b; cin >> a >> b; add(a, b); add(b, a); } cin >> u >> v; int cnt = 0; if (!dfs(u)) { cout << -1; } return 0;}

图连通性检查文档

图连通性检查方法

本文将介绍一个通过深度优先搜索（DFS）实现的图连通性检查方法。所提方法基于邻接矩阵表示，适用于稀疏图。

#include                     #include                     #include                     #include                     #include #include #include #include #include                 #define IL inline                #define x first                #define y second                typedef long long ll;                using namespace std;                const int M = 4010;                int n, m;                int h[M], ne[M], idx, e[M];                bool st[M];                int u, v;                void add(int a, int b) {                    e[idx] = b;                    ne[idx] = h[a];                    h[a] = idx++;                }                bool dfs(int u1) {                    if (u1 == v) return true;                    st[u1] = true;                    for (int i = h[u1]; ~i; i = ne[i]) {                        int j = e[i];                        if (st[j]) continue;                        if (dfs(j)) return true;                    }                    return false;                }                int main() {                    cin >> n >> m;                    memset(h, -1, sizeof(h));                    while (m--) {                        int a, b;                        cin >> a >> b;                        add(a, b);                        add(b, a);                    }                    cin >> u >> v;                    int cnt = 0;                    if (!dfs(u)) {                        cout << -1;                    }                    return 0;                }

注：本文为技术说明文档，旨在指导如何使用深度优先搜索检查图的连通性。该方法在计算图论中广泛应用。

上一篇：蓝桥训练 dp 背包

下一篇：蓝桥训练分考场

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

图连通性检查方法

发表评论

最新留言

关于作者

推荐文章