C++算法（图算法）

1. 图的深度优先搜索（DFS）

思路解析：

• DFS 是一种递归的图遍历算法，从起始节点开始，沿着一条路径尽可能深地访问，直到无法继续为止，然后回溯
• 使用 visited 数组标记已访问的节点，避免重复访问
• 可以用递归或栈实现，递归更简洁
• 时间复杂度：O(V + E)，V 是节点数，E 是边数

#include <iostream>
#include <vector>

using namespace std;

// DFS 递归实现
void DFS(int node, vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true;  // 标记当前节点为已访问
    cout << node << " ";   // 访问节点（可以是任何处理操作）
    
    // 遍历当前节点的所有邻居
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {  // 如果邻居未被访问
            DFS(neighbor, graph, visited);  // 递归访问邻居
        }
    }
}

int main() {
    int n = 6;  // 图中节点数
    vector<vector<int>> graph(n);  // 邻接表表示图
    
    // 构建图（无向图）
    graph[0] = {1, 2};
    graph[1] = {0, 3};
    graph[2] = {0, 4};
    graph[3] = {1};
    graph[4] = {2, 5};
    graph[5] = {4};
    
    vector<bool> visited(n, false);  // 初始化访问标记数组
    
    cout << "DFS 遍历结果: ";
    DFS(0, graph, visited);  // 从节点 0 开始 DFS
    cout << endl;
    
    return 0;
}

2. 图的广度优先搜索（BFS）

思路解析：

• BFS 是一种逐层遍历的算法，先访问起始节点，再访问其所有邻居，然后访问邻居的邻居
• 使用队列（FIFO）来实现，保证按层次顺序访问
• 适用于求最短路径（无权图）、层次遍历等问题
• 时间复杂度：O(V + E)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// BFS 实现
void BFS(int start, vector<vector<int>>& graph, vector<bool>& visited) {
    queue<int> q;  // 创建队列
    visited[start] = true;  // 标记起始节点为已访问
    q.push(start);  // 将起始节点入队
    
    while (!q.empty()) {
        int node = q.front();  // 取出队首节点
        q.pop();
        cout << node << " ";  // 访问节点
        
        // 遍历当前节点的所有邻居
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {  // 如果邻居未被访问
                visited[neighbor] = true;  // 标记为已访问
                q.push(neighbor);  // 将邻居入队
            }
        }
    }
}

int main() {
    int n = 6;
    vector<vector<int>> graph(n);
    
    // 构建图
    graph[0] = {1, 2};
    graph[1] = {0, 3};
    graph[2] = {0, 4};
    graph[3] = {1};
    graph[4] = {2, 5};
    graph[5] = {4};
    
    vector<bool> visited(n, false);
    
    cout << "BFS 遍历结果: ";
    BFS(0, graph, visited);
    cout << endl;
    
    return 0;
}

3. 拓扑排序（Topological Sorting）

思路解析：

• 拓扑排序用于有向无环图（DAG），将节点排成线性序列，使得对于每条有向边 (u, v)，u 都在 v 之前
• 使用 DFS 实现：递归访问所有节点，访问完一个节点后将其压入栈，最后栈中的顺序即为拓扑排序
• 应用场景：任务调度、课程安排、编译依赖等
• 时间复杂度：O(V + E)

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

// DFS 辅助函数，用于拓扑排序
void topologicalSortUtil(int node, vector<vector<int>>& graph, 
                         vector<bool>& visited, stack<int>& result) {
    visited[node] = true;  // 标记当前节点为已访问
    
    // 递归访问所有邻居
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            topologicalSortUtil(neighbor, graph, visited, result);
        }
    }
    
    // 当前节点的所有邻居都处理完后，将其压入栈
    result.push(node);
}

// 拓扑排序主函数
void topologicalSort(int n, vector<vector<int>>& graph) {
    vector<bool> visited(n, false);
    stack<int> result;  // 用栈存储拓扑排序结果
    
    // 对所有未访问的节点进行 DFS
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            topologicalSortUtil(i, graph, visited, result);
        }
    }
    
    // 输出拓扑排序结果
    cout << "拓扑排序结果: ";
    while (!result.empty()) {
        cout << result.top() << " ";
        result.pop();
    }
    cout << endl;
}

int main() {
    int n = 6;
    vector<vector<int>> graph(n);  // 有向图
    
    // 构建有向无环图
    graph[5] = {2, 0};
    graph[4] = {0, 1};
    graph[2] = {3};
    graph[3] = {};
    graph[0] = {};
    graph[1] = {};
    
    topologicalSort(n, graph);
    
    return 0;
}

4. 最短路径问题：Dijkstra 算法

思路解析：

• Dijkstra 算法用于求单源最短路径，适用于非负权图
• 贪心策略：每次选择当前距离最小的未访问节点，更新其邻居的距离
• 使用优先队列（最小堆）优化，每次取出距离最小的节点
• 时间复杂度：O((V + E) log V)

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

// Dijkstra 算法实现
void dijkstra(int src, vector<vector<pair<int, int>>>& graph, vector<int>& dist) {
    int n = graph.size();
    dist[src] = 0;  // 源节点到自己的距离为 0
    
    // 优先队列：pair<距离, 节点>，按距离从小到大排序
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, src});  // 将源节点入队
    
    while (!pq.empty()) {
        int u = pq.top().second;  // 当前距离最小的节点
        int d = pq.top().first;   // 当前节点的距离
        pq.pop();
        
        // 如果当前距离大于已记录的距离，跳过（已处理过更优的路径）
        if (d > dist[u]) continue;
        
        // 遍历当前节点的所有邻居
        for (auto& edge : graph[u]) {
            int v = edge.first;       // 邻居节点
            int weight = edge.second; // 边的权重
            
            // 松弛操作：如果通过 u 到 v 的距离更短，则更新
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});  // 将更新后的节点入队
            }
        }
    }
}

int main() {
    int n = 5;
    // 邻接表表示带权图：pair<邻居节点, 边权重>
    vector<vector<pair<int, int>>> graph(n);
    
    // 构建带权无向图
    graph[0] = {{1, 2}, {2, 4}};
    graph[1] = {{0, 2}, {2, 1}, {3, 7}};
    graph[2] = {{0, 4}, {1, 1}, {3, 3}};
    graph[3] = {{1, 7}, {2, 3}, {4, 1}};
    graph[4] = {{3, 1}};
    
    vector<int> dist(n, INT_MAX);  // 初始化距离为无穷大
    
    dijkstra(0, graph, dist);  // 从节点 0 开始
    
    // 输出结果
    cout << "从节点 0 到各节点的最短距离:\n";
    for (int i = 0; i < n; i++) {
        cout << "到节点 " << i << ": " << dist[i] << endl;
    }
    
    return 0;
}

5. 最短路径问题：Bellman-Ford 算法

思路解析：

• Bellman-Ford 算法可以处理负权边，并能检测负权环
• 核心思想：对所有边进行 V-1 次松弛操作，每次松弛都会更新最短路径
• 如果第 V 次松弛还能更新距离，说明存在负权环
• 时间复杂度：O(V * E)

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

// Bellman-Ford 算法实现
void bellmanFord(int src, vector<vector<pair<int, int>>>& graph, int n) {
    vector<int> dist(n, INT_MAX);  // 初始化距离为无穷大
    dist[src] = 0;  // 源节点到自己的距离为 0
    
    // 进行 V-1 次松弛操作
    for (int i = 0; i < n - 1; i++) {
        for (int u = 0; u < n; u++) {
            // 遍历节点 u 的所有边
            for (auto& edge : graph[u]) {
                int v = edge.first;       // 邻居节点
                int weight = edge.second; // 边的权重
                
                // 松弛操作
                if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                }
            }
        }
    }
    
    // 检测负权环：如果还能松弛，说明存在负权环
    for (int u = 0; u < n; u++) {
        for (auto& edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                cout << "图中存在负权环！" << endl;
                return;
            }
        }
    }
    
    // 输出结果
    cout << "从节点 " << src << " 到各节点的最短距离:\n";
    for (int i = 0; i < n; i++) {
        if (dist[i] == INT_MAX) {
            cout << "到节点 " << i << ": 不可达" << endl;
        } else {
            cout << "到节点 " << i << ": " << dist[i] << endl;
        }
    }
}

int main() {
    int n = 5;
    vector<vector<pair<int, int>>> graph(n);
    
    // 构建带权有向图（可以有负权边）
    graph[0] = {{1, -1}, {2, 4}};
    graph[1] = {{2, 3}, {3, 2}, {4, 2}};
    graph[2] = {};
    graph[3] = {{2, 5}, {1, 1}};
    graph[4] = {{3, -3}};
    
    bellmanFord(0, graph, n);
    
    return 0;
}

6. 最小生成树：Prim 算法

思路解析：

• Prim 算法用于求无向连通图的最小生成树（MST）
• 贪心策略：从任意节点开始,每次选择连接已访问节点和未访问节点的最小权重边
• 使用优先队列优化，维护当前可选的最小边
• 时间复杂度：O((V + E) log V)

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

// Prim 算法实现
int prim(vector<vector<pair<int, int>>>& graph, int n) {
    vector<bool> inMST(n, false);  // 标记节点是否在 MST 中
    vector<int> key(n, INT_MAX);   // 记录连接到 MST 的最小边权重
    
    // 优先队列：pair<权重, 节点>
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    int mstWeight = 0;  // MST 的总权重
    key[0] = 0;         // 从节点 0 开始
    pq.push({0, 0});
    
    while (!pq.empty()) {
        int u = pq.top().second;  // 当前权重最小的节点
        int weight = pq.top().first;
        pq.pop();
        
        // 如果节点已在 MST 中，跳过
        if (inMST[u]) continue;
        
        inMST[u] = true;      // 将节点加入 MST
        mstWeight += weight;  // 累加权重
        
        // 遍历当前节点的所有邻居
        for (auto& edge : graph[u]) {
            int v = edge.first;
            int w = edge.second;
            
            // 如果邻居不在 MST 中，且边权重更小，则更新
            if (!inMST[v] && w < key[v]) {
                key[v] = w;
                pq.push({w, v});
            }
        }
    }
    
    return mstWeight;
}

int main() {
    int n = 5;
    vector<vector<pair<int, int>>> graph(n);
    
    // 构建无向带权图
    graph[0] = {{1, 2}, {3, 6}};
    graph[1] = {{0, 2}, {2, 3}, {3, 8}, {4, 5}};
    graph[2] = {{1, 3}, {4, 7}};
    graph[3] = {{0, 6}, {1, 8}};
    graph[4] = {{1, 5}, {2, 7}};
    
    int mstWeight = prim(graph, n);
    cout << "最小生成树的总权重: " << mstWeight << endl;
    
    return 0;
}

7. 最小生成树：Kruskal 算法

思路解析：

• Kruskal 算法也用于求最小生成树，基于边的贪心算法
• 将所有边按权重排序，依次选择权重最小的边，如果该边不会形成环则加入 MST
• 使用并查集（Union-Find）来检测环
• 时间复杂度：O(E log E)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 边的结构体
struct Edge {
    int u, v, weight;
    bool operator<(const Edge& other) const {
        return weight < other.weight;  // 按权重升序排序
    }
};

// 并查集类
class UnionFind {
private:
    vector<int> parent, rank;
    
public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; i++) {
            parent[i] = i;  // 初始化每个节点的父节点为自己
        }
    }
    
    // 查找根节点（带路径压缩）
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 路径压缩
        }
        return parent[x];
    }
    
    // 合并两个集合（按秩合并）
    bool unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX == rootY) return false;  // 已在同一集合，会形成环
        
        // 按秩合并
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        return true;
    }
};

// Kruskal 算法实现
int kruskal(vector<Edge>& edges, int n) {
    sort(edges.begin(), edges.end());  // 按权重排序
    
    UnionFind uf(n);
    int mstWeight = 0;
    int edgeCount = 0;
    
    // 遍历所有边
    for (auto& edge : edges) {
        // 如果边的两个端点不在同一集合，则加入 MST
        if (uf.unite(edge.u, edge.v)) {
            mstWeight += edge.weight;
            edgeCount++;
            cout << "选择边: " << edge.u << " - " << edge.v 
                 << " (权重: " << edge.weight << ")" << endl;
            
            // MST 有 n-1 条边
            if (edgeCount == n - 1) break;
        }
    }
    
    return mstWeight;
}

int main() {
    int n = 5;  // 节点数
    vector<Edge> edges = {
        {0, 1, 2}, {0, 3, 6}, {1, 2, 3}, {1, 3, 8},
        {1, 4, 5}, {2, 4, 7}
    };
    
    int mstWeight = kruskal(edges, n);
    cout << "最小生成树的总权重: " << mstWeight << endl;
    
    return 0;
}

8. 图的连通性检测

思路解析：

• 检测无向图是否连通：从任意节点开始 DFS/BFS，看是否能访问所有节点
• 检测有向图的强连通性：需要使用 Kosaraju 或 Tarjan 算法
• 这里实现无向图的连通性检测
• 时间复杂度：O(V + E)

#include <iostream>
#include <vector>

using namespace std;

// DFS 遍历
void DFS(int node, vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            DFS(neighbor, graph, visited);
        }
    }
}

// 检测图的连通性
bool isConnected(vector<vector<int>>& graph, int n) {
    vector<bool> visited(n, false);
    
    // 从节点 0 开始 DFS
    DFS(0, graph, visited);
    
    // 检查是否所有节点都被访问
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            return false;  // 存在未访问的节点，图不连通
        }
    }
    return true;
}

// 计算连通分量数量
int countConnectedComponents(vector<vector<int>>& graph, int n) {
    vector<bool> visited(n, false);
    int count = 0;
    
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            DFS(i, graph, visited);
            count++;  // 每次 DFS 找到一个连通分量
        }
    }
    
    return count;
}

int main() {
    int n = 6;
    vector<vector<int>> graph(n);
    
    // 构建图（两个连通分量）
    graph[0] = {1, 2};
    graph[1] = {0};
    graph[2] = {0};
    graph[3] = {4, 5};
    graph[4] = {3};
    graph[5] = {3};
    
    if (isConnected(graph, n)) {
        cout << "图是连通的" << endl;
    } else {
        cout << "图不连通" << endl;
    }
    
    int components = countConnectedComponents(graph, n);
    cout << "连通分量数量: " << components << endl;
    
    return 0;
}

9. 岛屿数量问题（Number of Islands）

思路解析：

• 给定一个二维网格，'1' 表示陆地，'0' 表示水，求岛屿数量
• 岛屿是由相邻的陆地连接而成（上下左右四个方向）
• 使用 DFS 或 BFS 遍历每个陆地，将相连的陆地标记为已访问
• 每次 DFS/BFS 找到一个岛屿，计数加 1
• 时间复杂度：O(M * N)

#include <iostream>
#include <vector>

using namespace std;

// DFS 标记岛屿
void DFS(vector<vector<char>>& grid, int i, int j) {
    int m = grid.size();
    int n = grid[0].size();
    
    // 边界检查和条件检查
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {
        return;
    }
    
    grid[i][j] = '0';  // 标记为已访问（变成水）
    
    // 向四个方向递归
    DFS(grid, i + 1, j);  // 下
    DFS(grid, i - 1, j);  // 上
    DFS(grid, i, j + 1);  // 右
    DFS(grid, i, j - 1);  // 左
}

// 计算岛屿数量
int numIslands(vector<vector<char>>& grid) {
    if (grid.empty()) return 0;
    
    int m = grid.size();
    int n = grid[0].size();
    int count = 0;
    
    // 遍历整个网格
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {  // 发现陆地
                count++;              // 岛屿数量加 1
                DFS(grid, i, j);      // DFS 标记整个岛屿
            }
        }
    }
    
    return count;
}

int main() {
    vector<vector<char>> grid = {
        {'1', '1', '0', '0', '0'},
        {'1', '1', '0', '0', '0'},
        {'0', '0', '1', '0', '0'},
        {'0', '0', '0', '1', '1'}
    };
    
    int islands = numIslands(grid);
    cout << "岛屿数量: " << islands << endl;
    
    return 0;
}

10. 图的强连通分量（Strongly Connected Components）

思路解析：

• 强连通分量（SCC）：有向图中的极大强连通子图
• 使用 Kosaraju 算法：对原图进行 DFS，记录节点的完成顺序（后序遍历）构建反向图（所有边反向）按完成顺序的逆序对反向图进行 DFS，每次 DFS 找到一个 SCC
• 时间复杂度：O(V + E)

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

// 第一次 DFS，记录完成顺序
void DFS1(int node, vector<vector<int>>& graph, vector<bool>& visited, stack<int>& finishOrder) {
    visited[node] = true;
    
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            DFS1(neighbor, graph, visited, finishOrder);
        }
    }
    
    finishOrder.push(node);  // 记录完成顺序
}

// 第二次 DFS，在反向图上找 SCC
void DFS2(int node, vector<vector<int>>& reverseGraph, vector<bool>& visited, vector<int>& component) {
    visited[node] = true;
    component.push_back(node);
    
    for (int neighbor : reverseGraph[node]) {
        if (!visited[neighbor]) {
            DFS2(neighbor, reverseGraph, visited, component);
        }
    }
}

// Kosaraju 算法求强连通分量
vector<vector<int>> findSCC(vector<vector<int>>& graph, int n) {
    vector<bool> visited(n, false);
    stack<int> finishOrder;
    
    // 第一次 DFS，记录完成顺序
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            DFS1(i, graph, visited, finishOrder);
        }
    }
    
    // 构建反向图
    vector<vector<int>> reverseGraph(n);
    for (int u = 0; u < n; u++) {
        for (int v : graph[u]) {
            reverseGraph[v].push_back(u);  // 边反向
        }
    }
    
    // 第二次 DFS，按完成顺序的逆序处理
    fill(visited.begin(), visited.end(), false);
    vector<vector<int>> sccs;
    
    while (!finishOrder.empty()) {
        int node = finishOrder.top();
        finishOrder.pop();
        
        if (!visited[node]) {
            vector<int> component;
            DFS2(node, reverseGraph, visited, component);
            sccs.push_back(component);
        }
    }
    
    return sccs;
}

int main() {
    int n = 8;
    vector<vector<int>> graph(n);
    
    // 构建有向图
    graph[0] = {1};
    graph[1] = {2};
    graph[2] = {0, 3};
    graph[3] = {4};
    graph[4] = {5, 7};
    graph[5] = {6};
    graph[6] = {4};
    graph[7] = {};
    
    vector<vector<int>> sccs = findSCC(graph, n);
    
    cout << "强连通分量数量: " << sccs.size() << endl;
    for (int i = 0; i < sccs.size(); i++) {
        cout << "SCC " << i + 1 << ": ";
        for (int node : sccs[i]) {
            cout << node << " ";
        }
        cout << endl;
    }
    
    return 0;
}

11. 图中的环检测（Cycle Detection）

思路解析：

• 无向图环检测：使用 DFS，如果访问到已访问的节点（且不是父节点），则存在环
• 有向图环检测：使用 DFS + 递归栈，如果访问到递归栈中的节点，则存在环（也叫回边）
• 递归栈用于记录当前 DFS 路径上的节点
• 时间复杂度：O(V + E)

#include <iostream>
#include <vector>

using namespace std;

// ========== 无向图环检测 ==========
bool hasCycleUndirectedUtil(int node, int parent, vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true;
    
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            // 递归访问未访问的邻居
            if (hasCycleUndirectedUtil(neighbor, node, graph, visited)) {
                return true;
            }
        } else if (neighbor != parent) {
            // 访问到已访问的节点，且不是父节点，说明存在环
            return true;
        }
    }
    
    return false;
}

bool hasCycleUndirected(vector<vector<int>>& graph, int n) {
    vector<bool> visited(n, false);
    
    // 遍历所有节点（处理非连通图）
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            if (hasCycleUndirectedUtil(i, -1, graph, visited)) {
                return true;
            }
        }
    }
    
    return false;
}

// ========== 有向图环检测 ==========
bool hasCycleDirectedUtil(int node, vector<vector<int>>& graph, 
                          vector<bool>& visited, vector<bool>& recStack) {
    visited[node] = true;
    recStack[node] = true;  // 将当前节点加入递归栈
    
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            // 递归访问未访问的邻居
            if (hasCycleDirectedUtil(neighbor, graph, visited, recStack)) {
                return true;
            }
        } else if (recStack[neighbor]) {
            // 访问到递归栈中的节点，说明存在环（回边）
            return true;
        }
    }
    
    recStack[node] = false;  // 回溯时将节点从递归栈中移除
    return false;
}

bool hasCycleDirected(vector<vector<int>>& graph, int n) {
    vector<bool> visited(n, false);
    vector<bool> recStack(n, false);  // 递归栈，记录当前 DFS 路径
    
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            if (hasCycleDirectedUtil(i, graph, visited, recStack)) {
                return true;
            }
        }
    }
    
    return false;
}

int main() {
    // 测试无向图
    cout << "========== 无向图环检测 ==========" << endl;
    int n1 = 5;
    vector<vector<int>> undirectedGraph(n1);
    
    // 构建无向图（有环）
    undirectedGraph[0] = {1, 2};
    undirectedGraph[1] = {0, 2};
    undirectedGraph[2] = {0, 1, 3};
    undirectedGraph[3] = {2, 4};
    undirectedGraph[4] = {3};
    
    if (hasCycleUndirected(undirectedGraph, n1)) {
        cout << "无向图存在环" << endl;
    } else {
        cout << "无向图不存在环" << endl;
    }
    
    // 测试有向图
    cout << "\n========== 有向图环检测 ==========" << endl;
    int n2 = 4;
    vector<vector<int>> directedGraph(n2);
    
    // 构建有向图（有环）
    directedGraph[0] = {1};
    directedGraph[1] = {2};
    directedGraph[2] = {3};
    directedGraph[3] = {1};  // 形成环：1 -> 2 -> 3 -> 1
    
    if (hasCycleDirected(directedGraph, n2)) {
        cout << "有向图存在环" << endl;
    } else {
        cout << "有向图不存在环" << endl;
    }
    
    return 0;
}

12. 二分图检测（Bipartite Graph Detection）

思路解析：

• 二分图：图中的节点可以分成两个集合，使得所有边都连接不同集合的节点
• 检测方法：使用 BFS 或 DFS 进行染色，相邻节点染不同颜色
• 如果能成功染色（没有相邻节点颜色相同），则是二分图
• 应用场景：任务分配、匹配问题等
• 时间复杂度：O(V + E)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// ========== 使用 BFS 检测二分图 ==========
bool isBipartiteBFS(vector<vector<int>>& graph, int n) {
    vector<int> color(n, -1);  // -1 表示未染色，0 和 1 表示两种颜色
    
    // 遍历所有节点（处理非连通图）
    for (int start = 0; start < n; start++) {
        if (color[start] == -1) {  // 未染色的节点
            queue<int> q;
            q.push(start);
            color[start] = 0;  // 染成颜色 0
            
            while (!q.empty()) {
                int node = q.front();
                q.pop();
                
                // 遍历当前节点的所有邻居
                for (int neighbor : graph[node]) {
                    if (color[neighbor] == -1) {
                        // 邻居未染色，染成相反的颜色
                        color[neighbor] = 1 - color[node];
                        q.push(neighbor);
                    } else if (color[neighbor] == color[node]) {
                        // 邻居已染色，且颜色相同，不是二分图
                        return false;
                    }
                }
            }
        }
    }
    
    return true;
}

// ========== 使用 DFS 检测二分图 ==========
bool isBipartiteDFSUtil(int node, int c, vector<vector<int>>& graph, vector<int>& color) {
    color[node] = c;  // 给当前节点染色
    
    for (int neighbor : graph[node]) {
        if (color[neighbor] == -1) {
            // 邻居未染色，染成相反的颜色
            if (!isBipartiteDFSUtil(neighbor, 1 - c, graph, color)) {
                return false;
            }
        } else if (color[neighbor] == c) {
            // 邻居已染色，且颜色相同，不是二分图
            return false;
        }
    }
    
    return true;
}

bool isBipartiteDFS(vector<vector<int>>& graph, int n) {
    vector<int> color(n, -1);
    
    for (int i = 0; i < n; i++) {
        if (color[i] == -1) {
            if (!isBipartiteDFSUtil(i, 0, graph, color)) {
                return false;
            }
        }
    }
    
    return true;
}

int main() {
    // 测试二分图（是二分图）
    cout << "========== 测试 1：二分图 ==========" << endl;
    int n1 = 4;
    vector<vector<int>> graph1(n1);
    
    // 构建二分图
    graph1[0] = {1, 3};
    graph1[1] = {0, 2};
    graph1[2] = {1, 3};
    graph1[3] = {0, 2};
    
    if (isBipartiteBFS(graph1, n1)) {
        cout << "BFS 检测：是二分图" << endl;
    } else {
        cout << "BFS 检测：不是二分图" << endl;
    }
    
    if (isBipartiteDFS(graph1, n1)) {
        cout << "DFS 检测：是二分图" << endl;
    } else {
        cout << "DFS 检测：不是二分图" << endl;
    }
    
    // 测试非二分图（有奇数环）
    cout << "\n========== 测试 2：非二分图 ==========" << endl;
    int n2 = 3;
    vector<vector<int>> graph2(n2);
    
    // 构建非二分图（三角形）
    graph2[0] = {1, 2};
    graph2[1] = {0, 2};
    graph2[2] = {0, 1};
    
    if (isBipartiteBFS(graph2, n2)) {
        cout << "BFS 检测：是二分图" << endl;
    } else {
        cout << "BFS 检测：不是二分图" << endl;
    }
    
    if (isBipartiteDFS(graph2, n2)) {
        cout << "DFS 检测：是二分图" << endl;
    } else {
        cout << "DFS 检测：不是二分图" << endl;
    }
    
    return 0;
}