5.图论.题目2

题目

8.字符串接龙

题目链接

本题的直观思路如下图所示；但该题有两个问题：1.图中的线是如何连接起来的 2.如何确定起点到终点的最短路径。题中没给出节点之间的连线，条件是字符智能差一个。这里无向图求最短路，广搜最为合适，广搜只要搜到了终点，那么一定是最短的路径。因为广搜就是以起点中心向四周扩散的搜索。另外得注意

• 本题是无向图，需要用标记位，标记节点是否遍历过，否则就会死循环
• 使用set检查字符串是否出现过会更快
  

#include <iostream>
#include "vector"
#include "queue"
#include "unordered_map"
#include "unordered_set"using namespace std;int main(){string beginstr, endstr, strlist;int n;cin >>n;unordered_set<string> set; // store all the stringscin>> beginstr>> endstr;for(int i=0; i<n; i++) {cin >> strlist;set.insert(strlist);}queue<string> q;q.push(beginstr);unordered_map<string, int> visited;visited[beginstr] = 1;while(!q.empty()) {string curstr = q.front();q.pop();int path = visited[curstr];for(int i=0; i<curstr.size(); i++){string newstr = curstr;for(int j=0; j<26; j++){newstr[i] = 'a'+j;if(newstr == endstr){cout<< path+1<< endl;return 0;}if(set.find(newstr)!=set.end() && visited.find(newstr)==visited.end()){q.push(newstr);visited[newstr] = path+1;}}}}cout<< 0<< endl;return 0;
}

---

9.有向图的完全可达性

题目链接

题目要求判断节点的完全可达性；有向图搜索全路径的问题。 只能用深搜（DFS）或者广搜（BFS）来搜。
1.确认递归函数，参数：需要传入地图，需要知道key（知道下一步的节点）。同时需要一个数组，记录已经遍历的节点，这样才能判断有无将所有的节点已经遍历。
2.终止条件：因为在深度搜索时，没进入下一层搜索，是根据当前节点所对的邻接表key-list中的指向的节点，因此这是有限的遍历，当把邻接表所有的边遍历完，即可退出。

#include <iostream>
#include "vector"
#include "list"using namespace std;void dfs(const vector<list<int>>& graph, int key, vector<bool>& visited){list<int> adjs = graph[key];for(int adj: adjs){if(!visited[adj]){visited[adj] = true;dfs(graph, adj, visited);}}
}int main(){int n,m,s,t;cin>> n>> m;vector<list<int>> graph(n+1);while(m--){cin >>s >>t;graph[s].push_back(t);}vector<bool> visited(n+1,false);visited[1] = true;dfs(graph, 1, visited);for(int i=1; i<=n; i++){if(!visited[i]){cout<< -1<< endl;return 0;}}cout<< 1<< endl;return 0;
}

---

10.岛屿的周长

题目链接

求中间岛屿的周长，如果是使用dfs，bfs搜索算法的话，就是当发现并遍历岛屿时，每遍历一个节点，就计算其四周临近海水的边数，统计总数即可。
但其实本题是可以不适用dfs，bfs搜索算法，直接执行全图的遍历，当遍历到陆地时，检查其四周节点的情况，当四周是海水，或者超出图范围时，可认为是其边界。

#include <iostream>
#include "vector"using namespace std;int main(){int n,m,s,t;cin>> n>> m;vector<vector<int>> graph(n, vector<int>(m, 0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>> graph[i][j];}}int dir[4][2] = {0, 1, 1, 0,-1,0,0,-1};int res = 0;for(int i=0;i<n;i++) {for (int j = 0; j < m; j++) {if (graph[i][j] == 1) {for (auto &d: dir) {int x = i + d[0];int y = j + d[1];if(x<0 || x>=n || y<0 || y>=m || graph[x][y]==0) res++;}}}}cout<<res<<endl;return 0;
}

---

11.寻找存在的路径

题目链接

这题是并查集的基础题目，并查集解决的集合问题：1）判断两个节点在不在一个集合 2）将来两个节点添加到一个集合中

#include <iostream>
#include "vector"using namespace std;int n; // number of nodes
vector<int> father(n+1, 0);// Union-Find Set's initialize Fucntion
void init(){for(int i=0;i<=n;i++){father[i] = i;}
}// Union-Find Set's Find Function
int find(int u){return u == father[u]? u : father[u] = find(father[u]); // path compression 路径压缩
}// Union-Find Set's Union Function
void join(int u, int v){u = find(u);v = find(v);if(u!= v) {father[v] = u;}
}// Union-Finds Set's isSame Function
bool isSame(int u, int v){u = find(u);v = find(v);return u == v;
}int main(){int m, s, t, source , destination;cin>> n>> m;init();while(m--){cin>> s>> t;join(s, t);}cin>> source>> destination;if(isSame(source, destination)) cout<< 1<< endl;else cout<< 0<< endl;return 0;
}

---

12.冗余连接1

题目链接

题目说是无向图，返回一条可以删去的边，使得结果图是一个有着N个节点的树（即：只有一个根节点）。如果有多个答案，则返回二维数组中最后出现的边。因此我们可以从前向后遍历边，边的两个节点如果不是在通过一个集合，就加入同一个集合（即，同一个根节点）；如果两个节点已经在同一个集合，不添加改变，避免成环（无法成为树）。

#include <iostream>
#include "vector"using namespace std;int n; // number of nodes
vector<int> father(n+1, 0);void init(){for(int i=0;i<=n;i++){father[i] = i;}
}// Union-Find Set's Find Function
int find(int u){return u == father[u]? u : father[u] = find(father[u]); // path compression
}// Union-Find Set's Union Function
void join(int u, int v){u = find(u);v = find(v);if(u!= v) {father[v] = u;}
}// Union-Finds Set's isSame Function
bool isSame(int u, int v){u = find(u);v = find(v);return u == v;
}int main(){int s,t;cin>> n;init();for(int i=0;i<n;i++){cin>> s>> t;if(isSame(s, t)){cout<< s<< " "<< t<< endl;return 0;}else{join(s, t);}}return 0;
}

---

13.冗余连接2

题目链接
本题的本质是 ：有一个有向图，是由一颗有向树 + 一条有向边组成的 （所以此时这个图就不能称之为有向树），现在让我们找到那条边 把这条边删了，让这个图恢复为有向树，而且考虑若有多条边可以删除，请输出标准输入中最后出现的一条边。

有向树的特征是，节点的父子点是唯一的，即节点的入度是1；而且不能成环，必有一个节点的父子点是其自己，分为可以分为以下三种情况：
1.情况一：如果我们找到入度为2的点，那么删一条指向该节点的边就行了

2.情况二：节点3 的入度为 2，但在删除边的时候，只能删 这条边（节点1 -> 节点3），如果删这条边（节点4 -> 节点3），那么删后本图也不是有向树了（因为找不到根节点）

3.情况三：没有入度为2的点，说明 图中有环了，删除构成环的边（最后形成的）就可以了

给出代码

#include <iostream>
#include "vector"using namespace std;int n; // number of nodes
vector<int> father;void init(){for(int i=0;i<=n;i++){father[i] = i;}
}// Union-Find Set's Find Function
int find(int u){return u == father[u]? u : father[u] = find(father[u]); // path compression
}// Union-Find Set's Union Functionvoid join(int u, int v){u = find(u);v = find(v);if(u!= v) {father[v] = u;}
}// Union-Finds Set's isSame Function
bool isSame(int u, int v){u = find(u);v = find(v);return u == v;
}bool isTreeaftermove(const vector<vector<int>>& edges, int delete_index){init();for(int i=0;i<n;i++){if(i==delete_index) continue;if(isSame(edges[i][0], edges[i][1])) return false; // 出现环join(edges[i][0], edges[i][1]);}return true; // 无环
}void moveEdge(const vector<vector<int>>& edges){init();for(int i=0;i<n;i++){if(isSame(edges[i][0], edges[i][1])){cout<< edges[i][0]<< " " << edges[i][1]<< endl;return;}else{join(edges[i][0], edges[i][1]);}}return;
}int main(){int s,t;cin>> n;father.resize(n+1,0);vector<vector<int>> edges(n, vector<int>(2,0)); // 存储边vector<int> indegree(n+1, 0); // 记录t节点的入度for(int i=0;i<n;i++){cin>> s>> t;edges[i][0] = s;edges[i][1] = t;indegree[t]++;}vector<int> vec; // 记录edges中使得出现入度位2节点出现的边的下标for(int i=n-1;i>=0;i--){if(indegree[edges[i][1]]==2) vec.push_back(i);}if(!vec.empty()){// 处理入度为2的边的节点 vec中有且只有2个元素if(isTreeaftermove(edges, vec[0])){cout<< edges[vec[0]][0]<< " " << edges[vec[0]][1]<< endl;}else {cout << edges[vec[1]][0] << " " << edges[vec[1]][1] << endl;}return 0;}else{// 处理自成环的节点moveEdge(edges);return 1;}
}

---

14.寻宝

题目链接

本题是最小生成树的模板题，最小生成树 可以使用 prim算法 也可以使用 kruskal算法计算出来。

最小生成树是所有节点的最小连通子图， 即：以最小的成本（边的权值）将图中所有节点链接到一起。图中有n个节点，那么一定可以用 n - 1 条边将所有节点连接到一起。那么如何选择 这 n-1 条边 就是 最小生成树算法的任务所在。

prim算法核心就是三步，我称为prim三部曲，大家一定要熟悉这三步：

• 第一步，选距离生成树最近节点
• 第二步，最近节点加入生成树
• 第三步，更新非生成树节点到生成树的距离（即更新minDist数组）
  prim算法代码：

#include <iostream>
#include "vector"
#include "climits"using namespace std;int main(){int v, e; // 节点数，边数int x, y, k;cin>> v>> e;vector<vector<int>> graph(v+1, vector<int>(v+1, INT_MAX));for(int i=0; i<e; i++){cin>> x>> y>> k;graph[x][y] = k;graph[y][x] = k;}vector<int> minDist(v+1, INT_MAX);vector<bool> visited(v+1, false);vector<int> parent(v+1, -1);  // 用于记录每个节点i能被到达的父节点for(int i=1; i<=v; i++){// 从i=1出发，默认根节点是1int cur = -1;int minVal = INT_MAX;// 选择距离源点最近的节点作检查for(int j=1; j<=v; j++){if(!visited[j] && minDist[j] < minVal){minVal = minDist[j];cur = j;}}// 更新minDistvisited[cur] = true;for(int j=1; j<=v; j++){if(!visited[j] && graph[cur][j] < minDist[j]){minDist[j] = graph[cur][j];parent[j] = cur; // 记录边}}}int res = 0;for(int i=2; i<=v; i++){res += minDist[i];}cout<< res<< endl;return 0;
}

prim 算法是维护节点的集合，而 Kruskal 是维护边的集合。kruscal的思路：

• 边的权值排序，因为要优先选最小的边加入到生成树里
• 遍历排序后的边：1）如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环 2）如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合
  kruskal算法实现

在这里插入代码片