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

Leetcode127. 单词接龙

文章链接：代码随想录
题目链接：127. 单词接龙

思路：广搜搜出来直接就是最短路径，深搜还需要判断；广搜相当于先把这一层路径的单词下一步走法都扫出来再走下一步；而深搜找到一条路径就先走到头，再返回来走下一条路径，需要判断路径长度，麻烦
另外需要标记位，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.钥匙和房间

文章链接：代码随想录
题目链接：841.钥匙和房间

思路：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. 岛屿的周长

文章链接：代码随想录
题目链接：463. 岛屿的周长

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

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. 寻找图中是否存在路径

文章链接：代码随想录
题目链接：1971. 寻找图中是否存在路径

思路：并查集入门

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.冗余连接

文章链接：代码随想录
题目链接：684.冗余连接

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

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

文章链接：代码随想录
题目链接：685.冗余连接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);}
};