1971-寻找图中是否存在路径

LeetCode 1971. 寻找图中是否存在路径

有一个具有 n 个顶点的 双向 图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）。图中的边用一个二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接，并且没有顶点存在与自身相连的边。

请你确定是否存在从顶点 start 开始，到顶点 end 结束的 有效路径 。

给你数组 edges 和整数 n、start和end，如果从 start 到 end 存在 有效路径 ，则返回 true，否则返回 false 。

示例 1：

输入：n = 3, edges = [[0,1],[1,2],[2,0]], start = 0, end = 2
输出：true
解释：存在由顶点 0 到顶点 2 的路径:
- 0 → 1 → 2 
- 0 → 2

method 1: DFS

加上回溯会超时，因为如果一个节点找不到目标，那这个节点就不需要再访问了，所以不用回溯，加上回溯之后，后面可能会又访问到这个节点，导致超时

bool dfs(vector<vector<int>>& e, int index, int end, vector<bool>& used) {
    if (index == end) return true;
    if (used[index]) return false;
    used[index] = true;
    for (auto& v : e[index]) {
        if (dfs(e, v, end, used)) return true;
    }
    // used[index] = false; // 不用回溯
    return false;
}
bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
    vector<vector<int>> e(n);
    for (int i = 0; i < edges.size(); i++) {
        int u = edges[i][0], v = edges[i][1];
        e[u].push_back(v);
        e[v].push_back(u);
    }
    vector<bool> used(n, false);
    return dfs(e, source, destination, used);
}

method 2: BFS

bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
    vector<vector<int>> e(n);
    for (int i = 0; i < edges.size(); i++) {
        int u = edges[i][0], v = edges[i][1];
        e[u].push_back(v);
        e[v].push_back(u);
    }
    vector<bool> used(n, false);
    queue<int> q;
    q.push(source);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        if (x == destination) return true;
        for (auto& v : e[x]) {
            if (!used[v]) {
                used[v] = true;
                q.push(v);
            }
        }
    }
    return false;
}