c++给定无向图的顶点数、边数、边的信息以及任意两顶点信息，判定该两顶点之间是否存在路径。X组测试数据，对于每组测试数据， 第一行输入顶点数N（N<=100），边数M，数据之间空格分隔； 第二行输入M条边的信息（v1 v2表示边的顶点），数据之间由空格分隔。 第三行输入两顶点信息。若两顶点之间存在路径，输出YES，否则输出NO。

好的，我会为您解答这个问题。

首先，我们可以使用邻接矩阵或邻接表来存储无向图。这里我们选择邻接矩阵。

具体实现过程如下：

1. 定义一个二维数组adjMat[N][N]，其中N为顶点数。如果顶点i和j之间有边，则adjMat[i][j] = adjMat[j][i] = 1，否则adjMat[i][j] = adjMat[j][i] = 0。

2. 输入M条边的信息，同时更新adjMat数组。

3. 输入两顶点信息v1和v2，判断它们之间是否存在路径。我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来实现。

以DFS为例，具体实现过程如下：

- 定义一个visited[N]数组，表示每个顶点是否被访问过。初始时，visited数组所有元素都为false。
- 从v1开始进行DFS搜索，如果能够到达v2，则输出YES，否则输出NO。
- 在DFS搜索过程中，如果访问到一个未被访问过的顶点i，将visited[i]设为true，并继续从i开始进行DFS搜索。

完整的C++代码如下：

相关问题

无向图最小权顶点覆盖问题，边没有权值，顶点有c++实现

对于无权图的最小权顶点覆盖问题，可以使用二分图最大匹配求解。具体做法是将图中的点分为左右两个部分，对于每条边 (u, v)，在左部分的点 u 和右部分的点 v 之间连一条边，然后求解最大匹配，最小权顶点覆盖即为总点数减去最大匹配数。

以下是使用二分图最大匹配求解无向图最小权顶点覆盖问题的c++代码示例：

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 1005;

int n, m;
int link[MAXN];
bool vis[MAXN];
vector<int> G[MAXN];

bool dfs(int u) {
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!vis[v]) {
            vis[v] = true;
            if (link[v] == -1 || dfs(link[v])) {
                link[v] = u;
                return true;
            }
        }
    }
    return false;
}

int maxMatch() {
    int res = 0;
    memset(link, -1, sizeof(link));
    for (int i = 1; i <= n; i++) {
        memset(vis, false, sizeof(vis));
        if (dfs(i)) res++;
    }
    return res;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v + n);
        G[v + n].push_back(u);
    }
    int ans = n - maxMatch();
    cout << ans << endl;
    return 0;
}

其中，`G[i]`表示点 i 的邻接表，`link[i]`表示点 i 匹配的点，`vis[i]`表示点 i 是否被访问过。`dfs()`函数为匈牙利算法的递归函数，`maxMatch()`函数为求解最大匹配的函数，最小权顶点覆盖即为总点数减去最大匹配数。

c++无向图两点之间所有路径

要找出无向图中两点之间的所有路径，可以使用深度优先搜索（DFS）算法。下面是一份C++代码，可以实现该功能：

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100;  // 最大顶点数

vector<int> G[MAXN];  // 用 vector 存储图的邻接表

bool vis[MAXN];  // 标记数组，记录每个节点是否已被访问

vector<vector<int>> res;  // 存储所有路径的结果

void dfs(int u, int v, vector<int>& path) {
    if (u == v) {  // 如果到达目标节点，将路径存入结果中
        path.push_back(v);
        res.push_back(path);
        path.pop_back();
        return;
    }
    vis[u] = true;  // 标记当前节点已被访问
    path.push_back(u);  // 将当前节点加入路径中
    for (int i = 0; i < G[u].size(); i++) {  // 遍历当前节点的所有邻居
        int w = G[u][i];
        if (!vis[w]) {  // 如果邻居节点未被访问过
            dfs(w, v, path);  // 继续向下搜索
        }
    }
    vis[u] = false;  // 回溯时取消标记
    path.pop_back();  // 回溯时将当前节点从路径中删除
}

int main() {
    int n, m;  // n 表示节点数，m 表示边数
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;  // 一条边连接的两个节点
        cin >> u >> v;
        G[u].push_back(v);  // 添加一条边
        G[v].push_back(u);  // 由于是无向图，需要添加两条边
    }
    int s, t;  // 要求出的路径的起点和终点
    cin >> s >> t;
    vector<int> path;
    dfs(s, t, path);  // 搜索从 s 到 t 的所有路径
    for (int i = 0; i < res.size(); i++) {  // 输出所有路径
        for (int j = 0; j < res[i].size(); j++) {
            cout << res[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

在上面的代码中，我们使用邻接表来存储图。在 DFS 的过程中，我们使用一个标记数组 vis 来记录每个节点是否已被访问过，使用一个 vector<int> 类型的 path 变量来存储当前路径。如果当前节点 u 到达目标节点 v，我们就将当前路径存入结果 res 中。在回溯时，我们需要将当前节点从路径中删除，并将其标记为未访问，以便在搜索其他路径时重新访问它。最后，我们遍历结果 res 中的所有路径，并输出它们。