图论第三天|127. 单词接龙 841.钥匙和房间 463. 岛屿的周长 1971. 寻找图中是否存在路径 684.冗余连接 685.冗余连接II

Leetcode127. 单词接龙

思路：广搜搜出来直接就是最短路径，深搜还需要判断；广搜相当于先把这一层路径的单词下一步走法都扫出来再走下一步；而深搜找到一条路径就先走到头，再返回来走下一条路径，需要判断路径长度，麻烦
另外需要标记位，wordMap，避免死循环

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());

        if (wordSet.find(endWord) == wordSet.end()) return 0;

        unordered_map<string, int> wordMap;

        wordMap.insert(pair<string, int>(beginWord, 1));

        queue<string> que;
        que.push(beginWord);

        while(!que.empty()){
            string word = que.front();
            que.pop();
            int path = wordMap[word];
            for (int i = 0; i < word.size(); i++){
                string newword = word;
                for (int j = 0; j < 26; j++){
                    newword[i] = j + 'a';
                    if (newword == endWord) return path + 1;
                    if (wordSet.find(newword) != wordSet.end() && wordMap.find(newword) == wordMap.end()) {
                        wordMap.insert(pair<string, int>(newword, path + 1));
                        que.push(newword);
                    }


                }
            }
        }
        return 0;
    }
};

Leetcode841.钥匙和房间

思路：dfs

class Solution {
public:
    void dfs(vector<vector<int>>& rooms, vector<bool>& visited, int key){
        if (visited[key]) return;
        visited[key] = true;

        for (int i : rooms[key]){
            dfs(rooms, visited, i);
        }
    }
    
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        vector<bool> visited(rooms.size(), false);
        dfs(rooms, visited, 0);


        for(int i : visited){
            if (i == false) return false;
        }
        return true;
    }
};

Leetcode463. 岛屿的周长

思路：不用深搜或广搜，遍历就好，不要想复杂。

class Solution {
public:
    int count = 0;
    int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};    
    
    int islandPerimeter(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if (grid[i][j] == 1){
                    for (int k = 0; k < 4; k++){

                        int nex = i + dir[k][0];
                        int ney = j + dir[k][1];

                        if (nex < 0 || nex >= grid.size() || ney < 0 || ney >= grid[0].size() || grid[nex][ney] == 0){
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }
};

Leetcode1971. 寻找图中是否存在路径

思路：并查集入门

class Solution {
private:
    int n = 200005;
    vector<int> father = vector<int> (n);

    void init(){
        for (int i = 0; i < n; i++) father[i] = i;
    }

    int find(int u){
        return u == father[u] ? u : father[u] = find(father[u]);
    }

    bool isSame(int u, int v){
        u = find(u);
        v = find(v);
        return u == v;
    }

    void join(int u, int v){
        u = find(u);
        v = find(v);
        if (u == v) return ;
        father[v] = u;
    }


public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        init();
        for (int i = 0; i < edges.size(); i++){
            join(edges[i][0], edges[i][1]);
        }
        return isSame(source, destination);
    }
};

Leetcode684.冗余连接

思路：并查集入门，用于解决无向有环图问题

class Solution {
private:
    int n = 1005;
    vector<int> father = vector<int>(n);

    void init(){
        for (int i = 0; i < n; i++){
            father[i] = i;
        }
    }

    int find (int u){
        return u == father[u] ? u : father[u] = find(father[u]);
    }

    bool isSame(int u, int v){
        u = find(u);
        v = find(v);
        return u == v;
    }

    void join(int u, int v){
        u = find(u);
        v = find(v);
        if (u == v) return ;
        father[u] = v;
    }

public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        init();
        for (int i = 0; i < edges.size(); i++){
            if (isSame(edges[i][0], edges[i][1])) return edges[i];
            else join(edges[i][0], edges[i][1]);
        }
        return {};
    }
};

Leetcode685.冗余连接II

思路：将有向图问题拆解成两个无向图有环问题。
另外注意const int n = 1005; n前需加const，否则用n初始化数组会报错，因为n 是一个可变的值

class Solution {
private:
    const int n = 1005;
    vector<int> father = vector<int>(n);
    
    void init(){
        for (int i = 0; i < n; i++){
            father[i] = i;
        }
    }

    int find(int u){
        return u == father[u] ? u : father[u] = find(father[u]);
    }

    bool isSame(int u, int v){
        u = find(u);
        v = find(v);
        return u == v;
    }

    void join(int u, int v){
        u = find(u);
        v = find(v);
        if (u == v) return;
        father[v] = u;
    }

    vector<int> getRemoveEdge(const vector<vector<int>>& edges){
        init();
        for (int i = 0; i < edges.size(); i++){
            if (isSame(edges[i][0], edges[i][1])) return edges[i];
            join(edges[i][0], edges[i][1]);
        }
        return {};
    }

    bool isTree(const vector<vector<int>>& edges, int i){
        init();
        for (int j = 0; j < edges.size(); j++){
            if (j == i) continue;
            if (isSame(edges[j][0], edges[j][1])) return false;
            join(edges[j][0], edges[j][1]);
        }
        return true;
    }

public:
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int inDegree[1005] = {0};
        for (int i = 0; i < edges.size(); i++){
            inDegree[edges[i][1]]++;
        }

        vector<int> vec;

        for (int i = edges.size() - 1; i >= 0; i--){
            if(inDegree[edges[i][1]] == 2) vec.push_back(i);
        }

        if (vec.size() > 0){
            if (isTree(edges, vec[0])) return edges[vec[0]];
            else return edges[vec[1]];
        }

        return getRemoveEdge(edges);
    }
};

图论第三天打卡，目前随想录上的图论问题刷完，加油！！！