代码随想录算法训练营 | 图论 | DFS

98. 所有可达路径// DFS

1. #include <bits/stdc++.h>
2. using namespace std;
4. vector<vector<int>> result;
5. vector<int> path;
7. void dfs(const vector<list<int>> &graph, int i, int target) {
8.   if (i == target) {
9.     result.push_back(path);
10.     return;
11.   }
12.   for (int nums : graph[i]) {
13.     path.push_back(nums);
14.     dfs(graph, nums, target);
15.     path.pop_back();
16.   }
17. }
19. int main() {
20.   int n, m;
21.   cin >> n >> m;
22.   vector<list<int>> graph(n + 1);
23.   int temp, next;
24.   for (int i = 0; i < m; i++) {
25.     cin >> temp >> next;
26.     graph[temp].push_back(next);
27.   }
28.   path.push_back(1);
29.   dfs(graph, 1, n);
30.   if (result.size() == 0)
31.     cout<<-1<<endl;
32.   for (int i = 0; i < result.size(); i++) {
33.     for (int j = 0; j < result[i].size() - 1; j++) {
34.       cout << result[i][j] << " ";
35.     }
36.     cout << result[i][result[i].size() - 1] << endl;
37.   }
38. }

复制代码

99. 岛屿数量//。。感觉这题没须要拘泥于用什么搜刮。。

1. #include<bits/stdc++.h>
2. using namespace std;
5. void DFSfindsameIsland(vector<vector<bool>>& finded,const vector<vector<int>>& graph,int a,int b){
6.     if(a<0||b<0||a>graph.size()-1||b>graph[a].size()-1) return;
7.     else if(graph[a][b]==0) return;
8.     else if(graph[a][b]==1){
9.         if(finded[a][b]==false){
10.             finded[a][b]=true;
11.             DFSfindsameIsland(finded,graph,a,b+1);
12.             DFSfindsameIsland(finded,graph,a+1,b);
13.             DFSfindsameIsland(finded,graph,a,b-1);
14.             DFSfindsameIsland(finded,graph,a-1,b);
15.         }
16.         else return;
17.     }
18. }
19. int main(){
20.     int i,j;
21.     cin>>i>>j;
22.     vector<vector<int>> graph(i,vector<int> (j));
23.     for(int a=0;a<i;a++){
24.         for(int b=0;b<j;b++){
25.             cin>>graph[a][b];
26.         }
27.     }
28.     vector<vector<bool>> finded(i,vector<bool> (j,false));
29.     int result=0;
30.     for(int a=0;a<i;a++){
31.         for(int b=0;b<j;b++){
32.             if(graph[a][b]==1&&!finded[a][b]){
33.                 result++;
34.                 DFSfindsameIsland(finded,graph,a,b);
35.             }  
36.         }
37.     }
38.     cout<<result<<endl;     
39. }

复制代码

100. 岛屿的最大面积//偷懒了。随便拿上一题的代码改改就交了

1. #include<bits/stdc++.h>
2. using namespace std;
5. int DFSfindsameIsland(vector<vector<bool>>& finded,const vector<vector<int>>& graph,int a,int b){
6.     if(a<0||b<0||a>graph.size()-1||b>graph[a].size()-1) return 0;
7.     else if(graph[a][b]==0) return 0;
8.     else{
9.         if(finded[a][b]==false){
10.             int result=1;
11.             finded[a][b]=true;
12.             result+=DFSfindsameIsland(finded,graph,a,b+1);
13.             result+=DFSfindsameIsland(finded,graph,a+1,b);
14.             result+=DFSfindsameIsland(finded,graph,a,b-1);
15.             result+=DFSfindsameIsland(finded,graph,a-1,b);
16.             return result;
17.         }
18.         else return 0;
19.     }
20. }
21. int main(){
22.     int i,j;
23.     cin>>i>>j;
24.     vector<vector<int>> graph(i,vector<int> (j));
25.     for(int a=0;a<i;a++){
26.         for(int b=0;b<j;b++){
27.             cin>>graph[a][b];
28.         }
29.     }
30.     vector<vector<bool>> finded(i,vector<bool> (j,false));
31.     int result=0;int maxaera=0;
32.     for(int a=0;a<i;a++){
33.         for(int b=0;b<j;b++){
34.             if(graph[a][b]==1&&!finded[a][b]){
35.                 maxaera=max(maxaera,DFSfindsameIsland(finded,graph,a,b));
36.             }  
37.         }
38.     }
39.     cout<<maxaera<<endl;     
40. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。