深入探索图连通性：关节点检测与高级算法实现挑战

#include <iostream>
#include <vector>
#include <algorithm> // For std::min

class Graph {
public:
    int V; // 节点数量
    std::vector<std::vector<int>> adj; // 邻接列表
    std::vector<int> disc, low; // 发现时间与低链接值
    std::vector<bool> visited, isArticulationPoint; // 访问状态与是否为关节点
    int timer; // 时间戳计数器

    // 构造函数
    Graph(int V) : V(V), adj(V), disc(V), low(V), visited(V, false), isArticulationPoint(V, false), timer(0) {}

    // 添加无向边
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // DFS辅助函数，用于查找关节点
    void findArticulationPointsUtil(int u, int parent) {
        visited[u] = true;
        disc[u] = low[u] = ++timer; // 初始化发现时间与低链接值
        int children = 0; // 记录DFS树中u的子节点数量

        for (int v : adj[u]) {
            if (v == parent) continue; // 跳过父节点

            if (visited[v]) { // 如果v已被访问，则v是u的祖先节点（或u的兄弟节点，通过回边连接）
                low[u] = std::min(low[u], disc[v]); // 更新u的低链接值
            } else { // 如果v未被访问，则v是u的DFS树子节点
                children++;
                findArticulationPointsUtil(v, u); // 递归访问子节点v
                low[u] = std::min(low[u], low[v]); // 更新u的低链接值（考虑v子树的回边）

                // 关节点判断条件
                // 1. u是DFS树的根节点，且至少有两个子节点
                if (parent == -1 && children > 1) {
                    isArticulationPoint[u] = true;
                }
                // 2. u不是根节点，且它的一个子节点v无法通过回边到达u的任何真祖先节点
                if (parent != -1 && low[v] >= disc[u]) {
                    isArticulationPoint[u] = true;
                }
            }
        }
    }

    // 主函数，查找所有关节点
    void findArticulationPoints() {
        for (int i = 0; i < V; ++i) {
            if (!visited[i]) {
                findArticulationPointsUtil(i, -1); // 从未访问的节点开始DFS，-1表示无父节点
            }
        }

        std::cout << "Articulation Points (Cut Vertices): ";
        bool found = false;
        for (int i = 0; i < V; ++i) {
            if (isArticulationPoint[i]) {
                std::cout << i << " ";
                found = true;
            }
        }
        if (!found) {
            std::cout << "None";
        }
        std::cout << std::endl;
    }
};

int main() {
    // 示例图 1: 包含关节点
    // 0--1--2
    // |  |
    // 3--4
    // 关节点: 1, 3
    Graph g1(5);
    g1.addEdge(0, 1);
    g1.addEdge(1, 2);
    g1.addEdge(0, 3);
    g1.addEdge(3, 4);
    g1.addEdge(1, 4); // Added to create a cycle 0-1-4-3-0
    std::cout << "Graph 1:" << std::endl;
    g1.findArticulationPoints(); // Expected: 1 (if 0-3-4-1 forms a cycle, 1 is not AP if 0-3 and 1-4 are separate branches. Let's re-evaluate this example)

    // A clearer example for AP:
    // 0 -- 1 -- 2
    //      | \
    //      3 -- 4
    // Here, 1 is an AP. If 1 is removed, 0 is disconnected from {2,3,4}
    Graph g_clear_ap(5);
    g_clear_ap.addEdge(0, 1);
    g_clear_ap.addEdge(1, 2);
    g_clear_ap.addEdge(1, 3);
    g_clear_ap.addEdge(3, 4);
    std::cout << "\nGraph with clear AP (1):" << std::endl;
    g_clear_ap.findArticulationPoints(); // Expected: 1, (3 if 3-4 is a path)

    std::cout << "\n";

    // 示例图 2: 链状图
    // 0--1--2--3
    // 关节点: 1, 2
    Graph g2(4);
    g2.addEdge(0, 1);
    g2.addEdge(1, 2);
    g2.addEdge(2, 3);
    std::cout << "Graph 2:" << std::endl;
    g2.findArticulationPoints(); // Expected: 1, 2

    std::cout << "\n";

    // 示例图 3 (无关节点): 环状图
    // 0--1
    // |  |
    // 2--3
    Graph g3(4);
    g3.addEdge(0, 1);
    g3.addEdge(1, 3);
    g3.addEdge(3, 2);
    g3.addEdge(2, 0);
    std::cout << "Graph 3 (Cycle):" << std::endl;
    g3.findArticulationPoints(); // Expected: None

    return 0;
}