代码随想录算法训练营第五十三天|图论part4

110.字符串接龙

题目链接： 110. 字符串接龙 文章讲解： 代码随想录

 思路：

把每个字符串看成图的一个节点。

转换为求无权图两节点的的最短路径。求最短路径用bfs

#include #include #include #include #include using namespace std;unordered_mapmymap;bool canTransform(string a, string b) { int count = 0; if (a.size() != b.size())return false; int size = min(a.size(), b.size()); for (int i = 0; i < size; i++) { if (a[i] != b[i])count++; } if (count == 1)return true; else return false;}//广搜求最短路径int bfs(vector<vector>graph, int begin, int end) { queuemq; mq.push(begin); while (!mq.empty()) { int curStr = mq.front(); if (curStr == end) { return mymap[end]; } mq.pop(); for (int i = 0; i > n; cin >> beginStr >> endStr; vectorstrList; strList.push_back(beginStr); int size = n; //使用while（n--）会改变n的值 while (size--) { string str; cin >> str; strList.push_back(str); } strList.push_back(endStr); //构造图 vector<vector>graph(n + 2, vector(n + 2, false)); for (int i = 0; i < graph.size(); i++) { for (int j = 0; j < graph.size(); j++) { if (canTransform(strList[i], strList[j]))graph[i][j] = true; } } int ans = 0; ans = bfs(graph, 0, n + 1); cout << ans;}

105.有向图的完全可达性

题目链接：105. 有向图的完全联通

文章讲解：代码随想录

思路：

用深搜

逐渐遍历看第一个节点能不能到达其他节点

错误深搜：

#include #include using namespace std;bool dfs(vector<pair>graph, int begin, int end) { if (begin == end)return true; for (int i = 0; i > n >> k; vector<pair>graph; for (int i = 0; i > s >> t; graph.push_back({ s,t }); } int ans = 1; for (int i = 2; i <= n; i++) { if (!dfs(graph, 1, i)) { ans = -1; } } cout << ans;}

错误原因：

没有visited记录已经访问过的节点 ，导致陷入死循环。

#include #include using namespace std;bool dfs(vector<pair>graph,vector&visited, int begin, int end) { visited[begin]=true; //visited记录已经访问过的节点 if (begin == end)return true; for (int i = 0; i > n >> k; vector<pair>graph; for (int i = 0; i > s >> t; graph.push_back({ s,t }); } int ans = 1; for (int i = 2; i <= n; i++) { vectorvisited(n,false); if (!dfs(graph, visited,1, i)) { ans = -1; } } cout << ans;}

106.岛屿的周长

题目链接：106. 岛屿的周长

文章讲解：代码随想录

思路：

遍历所有陆地，统计其四个方向 如果是海 则边数+1

不要用惯性思维用深搜

#include #include using namespace std;int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};int main(){ int n,m; cin>>n>>m; vector<vector>grid(n,vector(m,0)); for(int i=0;i<n;i++){ for(int j=0;j>grid[i][j]; } } int ans=0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(grid[i][j]==1){ for(int k=0;k<4;k++){  int nextx=i+dir[k][0];  int nexty=j+dir[k][1];  if(nextx<0||nexty=grid.size()||nexty>=grid[0].size()){ ans+=1; continue;  }  if(grid[nextx][nexty]==0)ans++; } } } } cout<<ans;}