Graph-Medium

Abstract：leetcode图相关问题题解

面试题 04.01. Route Between Nodes LCCI

解法一：直接二元组bfs

每次访问如果失败删除一条边

• 超时，除非面向测试用例编程，

class Solution {
public:
    bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
        // if(n >= 100000) return graph[3][0] == 0 && graph[3][1] == 7;
        queue<int> q; q.push(start);
        while(!q.empty()) {
            int curr = q.front(); q.pop();
            for(vector<int>& v : graph) {
                if(v[0] == curr) {
                    if(v[1] == target) return true;
                    v[0] = -1;
                    q.push(v[1]);
                }
            }
        }
        return false;
    }
};

加上哈希优化，可以通过，但还是很慢

class Solution {
public:
    bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
        unordered_map<int, vector<int>> map;
        vector<bool> vis(n, false);
        for(vector v : graph) {
            map[v[0]].push_back(v[1]);
        }

        queue<int> q; q.push(start);
        while(!q.empty()) {
            int curr = q.front(); q.pop();
            if(vis[curr] == true) continue;
            for(int i = 0; i < map[curr].size(); i++) {
                if (map[curr][i] == target) return true;
                q.push(map[curr][i]);
            }
            vis[curr] = true;
        }
        return false;
    }
};