图论刷题

卡码网 98. 所有可达路径

使用邻接矩阵存储：

#include<iostream>
#include<vector>
using namespace std;vector<vector<int>>res;//收集符合条件的路径vector<int>path;//0节点到终点的路径//确定递归函数 参数和返回值void dfs(const vector<vector<int>>& graph,int x,int n){//确定终止条件if(x==n){res.push_back(path);return;}//确定单层递归逻辑for(int i=1;i<=n;i++){//寻找x节点指向的节点if(graph[x][i]==1){path.push_back(i);dfs(graph,i,n);path.pop_back();}}}
int main(){int n,m,s,t;//输入数据cin>>n>>m;vector<vector<int>>graph(n+1,vector<int>(n+1,0));while(m--){cin>>s>>t;graph[s][t]=1;}//遍历path.push_back(1);dfs(graph,1,n);//输出数据if(res.size()==0)cout<<-1<<endl;for(const vector<int>& pa:res){for(int i=0;i<pa.size()-1;i++){cout<<pa[i]<<' ';}cout<<pa[pa.size()-1]<<endl;}return 0;
}

使用邻接表存储：

#include<iostream>
#include<vector>
#include<list>
using namespace std;vector<vector<int>>res;//收集符合条件的路径vector<int>path;//0节点到终点的路径//确定递归函数 参数和返回值void dfs(const vector<list<int>>& graph,int x,int n){//确定终止条件if(x==n){res.push_back(path);return;}//确定单层递归逻辑for(int i:graph[x]){//寻找x节点指向的节点path.push_back(i);dfs(graph,i,n);path.pop_back();}}
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);}//遍历path.push_back(1);dfs(graph,1,n);//输出数据if(res.size()==0)cout<<-1<<endl;for(const vector<int>& pa:res){for(int i=0;i<pa.size()-1;i++){cout<<pa[i]<<' ';}cout<<pa[pa.size()-1]<<endl;}return 0;
}

卡码网 99. 岛屿数量

dfs搜索：

#include<iostream>
#include<vector>
using namespace std;int dir[4][2]={0,1,1,0,0,-1,-1,0};//右下左上 四个方向
//确定递归函数参数和返回值
void dfs(const vector<vector<int>>& grid,vector<vector<bool>>& visited,int x,int y){//确定终止条件//if(visited[x][y]==true||grid[x][y]==0)return;//不能加这个终止，我在上一层已经把状态变为true，我就是要遍历这个点的四周的，你//给我终止了，破坏了我的遍历//确定单层递归逻辑for(int i=0;i<4;i++){int nextx=x+dir[i][0];int nexty=y+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size())continue;if(grid[nextx][nexty]==1&&visited[nextx][nexty]==false){visited[nextx][nexty]=true;dfs(grid,visited,nextx,nexty);//不需要回溯，就是要dfs遍历一遍把周围的陆地都标记一下}}
}
int main(){//输入数据int n,m;cin>>n>>m;vector<vector<int>>grid(n,vector<int>(m,0));for(int x=0;x<n;x++){for(int y=0;y<m;y++){cin>>grid[x][y];}}vector<vector<bool>>visited(n,vector<bool>(m,false));//处理数据int res=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]==1&&visited[i][j]==false){res++;visited[i][j]=true;dfs(grid,visited,i,j);}}}cout<<res<<endl;return 0;
}

bfs搜索

#include<iostream>
#include<vector>
#include<queue>
using namespace std;int dir[4][2]={0,1,1,0,0,-1,-1,0};//右下左上 四个方向//确定递归函数参数和返回值
void bfs(const vector<vector<int>>& grid,vector<vector<bool>>& visited,int x,int y){//确定终止条件//确定单层递归逻辑queue<pair<int,int>>que;que.push({x,y});visited[x][y]=true;while(!que.empty()){pair<int,int>pa=que.front();que.pop();int curx=pa.first;int cury=pa.second;for(int i=0;i<4;i++){int nextx=curx+dir[i][0];int nexty=cury+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size())continue;if(grid[nextx][nexty]==1&&visited[nextx][nexty]==false){que.push({nextx,nexty});visited[nextx][nexty]=true;}}}}
int main(){//输入数据int n,m;cin>>n>>m;vector<vector<int>>grid(n,vector<int>(m,0));for(int x=0;x<n;x++){for(int y=0;y<m;y++){cin>>grid[x][y];}}vector<vector<bool>>visited(n,vector<bool>(m,false));//处理数据int res=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]==1&&visited[i][j]==false){res++;bfs(grid,visited,i,j);}}}cout<<res<<endl;return 0;
}

分析：对于这道题，dfs与bfs的做法，dfs函数中还有对dfs函数本身的调用；bfs函数中没有对bfs函数本身的调用，bfs做法中，对一个点进行bfs函数，把这个点压入队列中，让后从队列中取出点，对点的四周进行遍历，如果符合条件，就把点压入队列中，让后函数一直持续从队列中取数进行遍历，直到队列中为空。

100. 岛屿的最大面积

dfs法一：（dfs函数处理下一个节点，不需要再写终止条件，因为终止条件包含在单层循环处理中）

#include<iostream>
#include<vector>
using namespace std;int dir[4][2]={0,1,1,0,0,-1,-1,0};
int count=0;
//dfs处理下一个节点
//确定递归函数参数和返回值
void dfs(vector<vector<int>>& grid,vector<vector<bool>>& visited,int x,int y){for(int i=0;i<4;i++){int nextx=x+dir[i][0];int nexty=y+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size()) continue;if(visited[nextx][nexty]==false&&grid[nextx][nexty]==1){count++;visited[nextx][nexty]=true;dfs(grid,visited,nextx,nexty);}}
}int main(){//输入数据int res=0;int n,m;cin>>n>>m;vector<vector<int>>grid(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>grid[i][j];}}vector<vector<bool>>visited(n,vector<bool>(m,false));//处理数据for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]==1&&visited[i][j]==false){count=1;visited[i][j]=true;dfs(grid,visited,i,j);res=max(count,res);}}}cout<<res<<endl;return 0;
}

dfs法二（dfs处理当前节点，需要写终止条件）

#include<iostream>
#include<vector>
using namespace std;int dir[4][2]={0,1,1,0,0,-1,-1,0};
int count=0;
//dfs处理当前节点
//确定递归函数参数和返回值
void dfs(vector<vector<int>>& grid,vector<vector<bool>>& visited,int x,int y){//确定终止条件if(grid[x][y]==0||visited[x][y]==true) return;//确定单层递归逻辑count++;visited[x][y]=true;for(int i=0;i<4;i++){int nextx=x+dir[i][0];int nexty=y+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size()) continue;dfs(grid,visited,nextx,nexty);}
}int main(){//输入数据int res=0;int n,m;cin>>n>>m;vector<vector<int>>grid(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>grid[i][j];}}vector<vector<bool>>visited(n,vector<bool>(m,false));//处理数据for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]==1&&visited[i][j]==false){count=0;dfs(grid,visited,i,j);res=max(count,res);}}}cout<<res<<endl;return 0;
}

方法三：（bfs遍历）

#include<iostream>
#include<vector>
#include<queue>
using namespace std;int dir[4][2]={0,1,1,0,0,-1,-1,0};
int count=0;
//dfs处理当前节点
//确定递归函数参数和返回值
void bfs(vector<vector<int>>& grid,vector<vector<bool>>& visited,int x,int y){//确定单层递归逻辑queue<pair<int,int>>que;que.push({x,y});count++;visited[x][y]=true;while(!que.empty()){pair<int,int>pa=que.front();que.pop();int xx=pa.first;int yy=pa.second;for(int i=0;i<4;i++){int nextx=xx+dir[i][0];int nexty=yy+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size()) continue;if(grid[nextx][nexty]==1&&visited[nextx][nexty]==false){que.push({nextx,nexty});count++;visited[nextx][nexty]=true;}}}
}int main(){//输入数据int res=0;int n,m;cin>>n>>m;vector<vector<int>>grid(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>grid[i][j];}}vector<vector<bool>>visited(n,vector<bool>(m,false));//处理数据for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]==1&&visited[i][j]==false){count=0;bfs(grid,visited,i,j);res=max(count,res);}}}cout<<res<<endl;return 0;
}

101. 孤岛的总面积

用dfs遍历

#include<iostream>
#include<vector>
using namespace std;
int dir[4][2]={0,1,1,0,0,-1,-1,0};
//确定递归函数参数和返回值
//该dfs是为了把靠边缘的岛屿变成海洋
void dfs(vector<vector<int>>& grid,int x,int y){//确定单层递归逻辑grid[x][y]=0;for(int i=0;i<4;i++){int nextx=x+dir[i][0];int nexty=y+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size()){continue;}if(grid[nextx][nexty]==0) continue;dfs(grid,nextx,nexty);}}
int main(){//输入数据int n,m;cin>>n>>m;vector<vector<int>>grid(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>grid[i][j];}}//处理数据//遍历挨着边缘的岛屿for(int i=0;i<n;i++){if(grid[i][0]==1) dfs(grid,i,0);if(grid[i][m-1]==1) dfs(grid,i,m-1);}for(int j=0;j<m;j++){if(grid[0][j]==1) dfs(grid,0,j);if(grid[n-1][j]==1) dfs(grid,n-1,j);}int res=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]==1)res++;}}cout<<res<<endl;return 0;
}

使用bfs遍历：

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int dir[4][2]={0,1,1,0,0,-1,-1,0};
//确定递归函数参数和返回值
//该bfs是为了把靠边缘的岛屿变成海洋
void bfs(vector<vector<int>>& grid,int x,int y){//确定单层递归逻辑grid[x][y]=0;queue<pair<int,int>>que;que.push({x,y});while(!que.empty()){pair<int,int>pa;pa=que.front();que.pop();int xx=pa.first;int yy=pa.second;for(int i=0;i<4;i++){int nextx=xx+dir[i][0];int nexty=yy+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size()){continue;}if(grid[nextx][nexty]==0) continue;que.push({nextx,nexty});grid[nextx][nexty]=0;}}}
int main(){//输入数据int n,m;cin>>n>>m;vector<vector<int>>grid(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>grid[i][j];}}//处理数据//遍历挨着边缘的岛屿for(int i=0;i<n;i++){if(grid[i][0]==1) bfs(grid,i,0);if(grid[i][m-1]==1) bfs(grid,i,m-1);}for(int j=0;j<m;j++){if(grid[0][j]==1) bfs(grid,0,j);if(grid[n-1][j]==1) bfs(grid,n-1,j);}int res=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]==1)res++;}}cout<<res<<endl;return 0;
}

102. 沉没孤岛

使用dfs遍历

#include<iostream>
#include<vector>
using namespace std;
int dir[4][2]={0,1,1,0,0,-1,-1,0};
//确定递归函数参数和返回值
//该dfs是为了把靠边缘的岛屿用2标记，让后主函数中再遍历把2变成1,1变成0
void dfs(vector<vector<int>>& grid,int x,int y){//确定单层递归逻辑grid[x][y]=2;for(int i=0;i<4;i++){int nextx=x+dir[i][0];int nexty=y+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size()){continue;}if(grid[nextx][nexty]==0||grid[nextx][nexty]==2) continue;dfs(grid,nextx,nexty);}}
int main(){//输入数据int n,m;cin>>n>>m;vector<vector<int>>grid(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>grid[i][j];}}//处理数据//遍历挨着边缘的岛屿for(int i=0;i<n;i++){if(grid[i][0]==1) dfs(grid,i,0);if(grid[i][m-1]==1) dfs(grid,i,m-1);}for(int j=0;j<m;j++){if(grid[0][j]==1) dfs(grid,0,j);if(grid[n-1][j]==1) dfs(grid,n-1,j);}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]==1) grid[i][j]=0;if(grid[i][j]==2) grid[i][j]=1;}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<grid[i][j]<<' ';}cout<<endl;}return 0;
}

使用bfs遍历

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int dir[4][2]={0,1,1,0,0,-1,-1,0};
//确定递归函数参数和返回值
//该bfs是为了把靠边缘的岛屿用2标记，让后主函数中再遍历把2变成1,1变成0
void bfs(vector<vector<int>>& grid,int x,int y){//确定单层递归逻辑grid[x][y]=2;queue<pair<int,int>>que;que.push({x,y});while(!que.empty()){pair<int,int>pa;pa=que.front();que.pop();int xx=pa.first;int yy=pa.second;for(int i=0;i<4;i++){int nextx=xx+dir[i][0];int nexty=yy+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size()){continue;}if(grid[nextx][nexty]==0||grid[nextx][nexty]==2) continue;que.push({nextx,nexty});grid[nextx][nexty]=2;}}}
int main(){//输入数据int n,m;cin>>n>>m;vector<vector<int>>grid(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>grid[i][j];}}//处理数据//遍历挨着边缘的岛屿for(int i=0;i<n;i++){if(grid[i][0]==1) bfs(grid,i,0);if(grid[i][m-1]==1) bfs(grid,i,m-1);}for(int j=0;j<m;j++){if(grid[0][j]==1) bfs(grid,0,j);if(grid[n-1][j]==1) bfs(grid,n-1,j);}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]==1)grid[i][j]=0;if(grid[i][j]==2) grid[i][j]=1;}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<grid[i][j]<<' ';}cout<<endl;}return 0;
}

103. 水流问题

#include<iostream>
#include<vector>
using namespace std;int dir[4][2]={0,1,1,0,0,-1,-1,0};//确定递归函数 参数
//该dfs遍历，是对当前节点进行处理。从边缘逆流遍历，标记能到达边缘的坐标
void dfs(vector<vector<int>>& grid,vector<vector<bool>>& visited,int x,int y){//确定终止条件if(visited[x][y]==true) return;//确定单层递归逻辑visited[x][y]=true;for(int i=0;i<4;i++){int nextx=x+dir[i][0];int nexty=y+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size()){continue;}if(grid[x][y]>grid[nextx][nexty]) continue;dfs(grid,visited,nextx,nexty);}
}int main(){//输入数据int n,m;cin>>n>>m;vector<vector<int>>grid(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>grid[i][j];}}//处理数据vector<vector<bool>>firstBorder(n,vector<bool>(m,false));vector<vector<bool>>secondBorder(n,vector<bool>(m,false));//从边缘进行dfs遍历，标记目的单元格for(int i=0;i<n;i++){dfs(grid,firstBorder,i,0);//左侧dfs(grid,secondBorder,i,m-1);//右侧}for(int j=0;j<m;j++){dfs(grid,firstBorder,0,j);//上侧dfs(grid,secondBorder,n-1,j);//下侧}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(firstBorder[i][j]&&secondBorder[i][j]) cout<<i<<' '<<j<<endl;}}return 0;
}

104. 建造最大岛屿

#include<iostream>
#include<vector>
#include<unordered_map>
#include<unordered_set>
using namespace std;
int dir[4][2]={0,1,1,0,-1,0,0,-1};
int count;
//确定递归函数参数
//该dfs是将每个岛屿染成不同的颜色，并计算每个岛屿的面积大小
void dfs(vector<vector<int>>& grid,vector<vector<bool>>& visited,int x,int y,int mark){//确定终止条件if(grid[x][y]==0||visited[x][y]) return;//确定单层递归逻辑visited[x][y]=true;count++;grid[x][y]=mark;for(int i=0;i<4;i++){int nextx=x+dir[i][0];int nexty=y+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size()) continue;dfs(grid,visited,nextx,nexty,mark);}
}int main(){//输入数据int n,m;cin>>n>>m;vector<vector<int>>grid(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>grid[i][j];}}vector<vector<bool>>visited(n,vector<bool>(m,false));//处理数据unordered_map<int,int> gridNum;//记录每个岛屿的面积int mark=2;//记录每个岛屿的编号bool isAllGrid=true;//标记是否整个地图都是陆地for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]==0)isAllGrid=false;if(visited[i][j]==false&&grid[i][j]==1){count=0;dfs(grid,visited,i,j,mark);gridNum[mark]=count;mark++;}}}if(isAllGrid){cout<<n*m<<endl;return 0;}//根据添加陆地的位置，计算周边岛屿面积之和int res=0;//记录最后结果unordered_set<int>visitedGrid;//标记访问过的岛屿for(int i=0;i<n;i++){for(int j=0;j<m;j++){count=1;//记录连接之后的岛屿数量visitedGrid.clear();//每次使用时清空if(grid[i][j]==0){for(int k=0;k<4;k++){int nearx=i+dir[k][0];int neary=j+dir[k][1];if(nearx<0||nearx>=grid.size()||neary<0||neary>=grid[0].size()){continue;}if(visitedGrid.count(grid[nearx][neary]))continue;//添加过的岛屿不要重复添加count+=gridNum[grid[nearx][neary]];visitedGrid.insert(grid[nearx][neary]);}}res=max(res,count);}}cout<<res<<endl;return 0;
}

思路真的感觉很难想，而且代码很难实现。不过这道题应该还是要练图论的遍历，用的dfs遍历，感觉对图论的遍历更加掌握了。

110. 字符串接龙

#include<iostream>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<queue>
#include<string>
using namespace std;
int main(){//输入数据int n;cin>>n;string str,beginStr,endStr;cin>>beginStr>>endStr;unordered_set<string> strSet;for(int i=0;i<n;i++){cin>>str;strSet.insert(str);}//处理数据//转换的字符串之间只相差一个字符，字符串之间的连接形成了一个无向图，//遍历无向图，找到最短路径，使用广搜。//尝试替换每一个字符，如果在set字典中找到，并且没有没遍历过，//就可以加入que中，加入map中保存queue<string>que;que.push(beginStr);//初始化队列unordered_map<string,int>strMap;//map用来记录遍历长度，验证是否遍历过strMap.insert(pair<string,int>(beginStr,1));//初始化mapwhile(!que.empty()){string word=que.front();que.pop();int path=strMap[word];//轮流替换每个字符for(int i=0;i<word.size();i++){string newword=word;//不能在原本的字符上直接替换//尝试替换26个字符for(int j=0;j<26;j++){newword[i]=j+'a';if(newword==endStr){cout<<path+1<<endl;return 0;}if(strSet.find(newword)!=strSet.end()&&strMap.find(newword)==strMap.end()){que.push(newword);strMap.insert(pair<string,int>(newword,path+1));}}}}cout<<0<<endl;//没找到
}

105. 有向图的完全可达性

#include<iostream>
#include<list>
#include<vector>
using namespace std;//确定递归函数参数  使用dfs遍历
void dfs(const vector<list<int>>& grid,vector<bool>& visited,int key){//dfs处理当前节点if(visited[key]) return;//确定单层递归逻辑visited[key]=true;list<int>keys=grid[key];for(int key : keys){dfs(grid,visited,key);}
}int main(){//输入数据int n,k,s,t;cin>>n>>k;//使用邻接表保存图vector<list<int>> grid(n+1);while(k--){cin>>s>>t;grid[s].push_back(t);}//处理数据vector<bool> visited(n+1,false);dfs(grid,visited,1);for(int i=1;i<=n;i++){if(visited[i]==false) {cout<<-1<<endl;return 0;}}cout<<1<<endl;return 0;
}

dfs遍历 细微差别

#include<iostream>
#include<list>
#include<vector>
using namespace std;//确定递归函数参数  使用dfs遍历
void dfs(const vector<list<int>>& grid,vector<bool>& visited,int key){//dfs处理下一个节点//确定单层递归逻辑list<int>keys=grid[key];for(int key : keys){if(visited[key])continue;visited[key]=true;dfs(grid,visited,key);}
}int main(){//输入数据int n,k,s,t;cin>>n>>k;//使用邻接表保存图vector<list<int>> grid(n+1);while(k--){cin>>s>>t;grid[s].push_back(t);}//处理数据vector<bool> visited(n+1,false);visited[1]=true;dfs(grid,visited,1);for(int i=1;i<=n;i++){if(visited[i]==false) {cout<<-1<<endl;return 0;}}cout<<1<<endl;return 0;
}

通过bfs遍历

#include<iostream>
#include<list>
#include<vector>
#include<queue>
using namespace std;//确定递归函数参数  使用bfs遍历
void bfs(const vector<list<int>>& grid,vector<bool>& visited,int key){//确定单层递归逻辑queue<int>que;que.push(key);while(!que.empty()){int cur=que.front();que.pop();list<int>keys=grid[cur];for(int key:keys){if(visited[key]) continue;visited[key]=true;que.push(key);}}
}int main(){//输入数据int n,k,s,t;cin>>n>>k;//使用邻接表保存图vector<list<int>> grid(n+1);while(k--){cin>>s>>t;grid[s].push_back(t);}//处理数据vector<bool> visited(n+1,false);visited[1]=true;bfs(grid,visited,1);for(int i=1;i<=n;i++){if(visited[i]==false) {cout<<-1<<endl;return 0;}}cout<<1<<endl;return 0;
}

106. 岛屿的周长

#include<iostream>
#include<vector>
using namespace std;
int dir[4][2]={0,1,1,0,-1,0,0,-1};
int main(){int n,m;cin>>n>>m;vector<vector<int>>grid(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>grid[i][j];}}int res=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 x=i+dir[k][0];int y=j+dir[k][1];if(x<0||x>=n||y<0||y>=m||grid[x][y]==0)res++;}}}}cout<<res<<endl;return 0;
}

107. 寻找存在的路径

#include<iostream>
#include<vector>
using namespace std;
//确定节点数量
int n=105;
//根节点数组
vector<int>father(n,0);
//并查集初始化
void init(){for(int i=0;i<n;i++){father[i]=i;}
}
//并查集里寻根过程
int find(int u){return father[u]==u?u:father[u]=find(father[u]);
}
//判断u和v是否同一个根
bool isSame(int u,int v){u=find(u);v=find(v);return u==v;
}
//将v->u加入到并查集中
void ioin(int u,int v){u=find(u);v=find(v);if(u==v) return ;father[v]=u;
}
int main(){int m,s,t,source,destination;cin>>n>>m;init();for(int i=0;i<m;i++){cin>>s>>t;ioin(s,t);}cin>>source>>destination;if(isSame(source,destination))cout<<1<<endl;else cout<<0<<endl;return 0;
}

108. 冗余连接

#include<iostream>
#include<vector>
using namespace std;
//确定节点个数
int n=1005;
vector<int>father(n,0);
//初始化并查集
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;
}
//将v->u加入到并查集中
void join(int u,int v){u=find(u);v=find(v);if(u==v)return;father[v]=u;
}
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);}
}

109. 冗余连接II

#include<iostream>
#include<vector>
using namespace std;int n=1005;
vector<int>father(n,0);
//并查集初始化
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;
}
//将v->u加入并查集中
void join(int u,int v){u=find(u);v=find(v);if(u==v)return;father[v]=u;
}
bool isTreeAfterRemoveEdge(vector<vector<int>>& edges,int deleedge){//删除某边，利用并查集看是否构成有向树。或者删除另一条边。init();for(int i=0;i<n;i++){if(i==deleedge) continue;if(isSame(edges[i][0],edges[i][1])){return false;}join(edges[i][0],edges[i][1]);}return true;}
void getRemoveEdge(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;}join(edges[i][0],edges[i][1]);}}
int main(){//输入数据int s,t;cin>>n;vector<vector<int>>edges;//保存有向边vector<int>inDegree(n,0);for(int i=0;i<n;i++){cin>>s>>t;inDegree[t]++;//入度加一edges.push_back({s,t});}//处理数据  考虑三种情况//寻找有没有入度为2的，如果有，找到对应的两条边，删除某边，利用isTreeAfterRemoveEdge函数//为了保证最先删除的是最后输入的边，将两条边提取出来，按一定顺序尝试删除//情况三，入度没有2的，则是构成了单向环，利用getMoveEdge函数vector<int>vec;//记录指向入度为2的点//寻找度为2的for(int i=n-1;i>=0;i--){if(inDegree[edges[i][1]]==2){vec.push_back(i);}}//情况一,二if(vec.size()==2){if(isTreeAfterRemoveEdge(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;}//情况三getRemoveEdge(edges);}

53. 寻宝（第七期模拟笔试）

最小生成树 prim算法

#include<iostream>
#include<vector>
#include<climits>
using namespace std;int main(){int v,e,s,p,t;cin>>v>>e;vector<vector<int>>grid(v+1,vector<int>(v+1,10001));//存储图for(int i=1;i<=e;i++){cin>>s>>p>>t;grid[s][p]=t;grid[p][s]=t;//存储边及权值}vector<bool>isIntree(v+1,false);//是否在树里//所有节点到最小生成树的最小距离vector<int>minDist(v+1,10001);//需要执行n-1次三部曲，将边加入到最小生成树中for(int i=1;i<v;i++){int cur=-1;//要加入最小生成树的节点int minVal=INT_MAX;//非最小生成树节点到树的最短距离//prim第一步 选距离最小生成树最近的节点//条件：1.不在最小生成树里，//2.距离最小生成树最近的节点for(int j=1;j<=v;j++){if(!isIntree[j]&&minDist[j]<minVal){cur=j;minVal=minDist[j];}}//prim第二步 节点加入树isIntree[cur]=true;//rim第三步 更新非树节点到树的最小距离//只需要更新与新添加到树中节点相关的节点for(int j=1;j<=v;j++){if(!isIntree[j]&&grid[cur][j]<minDist[j]){minDist[j]=grid[cur][j];}}}int res=0;for(int i=2;i<=v;i++){res+=minDist[i];}cout<<res<<endl;return 0;
}

53. 寻宝（第七期模拟笔试）

最小生成树 kruskal算法

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;int n=10001;//节点数量
vector<int> father(n,0);
//初始化并查集
void init(){for(int i=1;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;
}
//将v->u加入到并查集中
void join(int u,int v){u=find(u);v=find(v);if(u==v)return;father[v]=u;
}struct edge{int l,r,val;
};
int main(){//输入数据int v,e,r,s,t;cin>>v>>e;vector<edge>edges(e+1);for(int i=1;i<=e;i++){cin>>r>>s>>t;edges.push_back({r,s,t});}//处理数据 //为edges排序，接着遍历，如果不构成环，就把边加入到并查集中，//同时累加权值int res_val=0;init();sort(edges.begin(),edges.end(),[](const edge& a,const edge& b){return a.val<b.val;});for(edge eg:edges){int i=find(eg.l);int j=find(eg.r);if(i!=j){res_val+=eg.val;join(i,j);}}cout<<res_val<<endl;return 0;
}

117. 软件构建

#include<iostream>
#include<vector>
#include<unordered_map>
#include<queue>
using namespace std;int main(){//输入数据int n,m,s,t;cin>>n>>m;unordered_map<int,vector<int>>umap(n);//记录文件间依赖关系vector<int>inDegree(n,0);for(int i=0;i<m;i++){cin>>s>>t;//先处理s再处理tumap[s].push_back(t);inDegree[t]++;//t的入度+1}//处理数据//1.找到入度为0的点，2.让其后缀节点入度减一。重复这两点queue<int>que;for(int i=0;i<n;i++){if(inDegree[i]==0) que.push(i);}vector<int>res;//记录处理顺序结果while(!que.empty()){int cur=que.front();que.pop();res.push_back(cur);vector<int>files;//保存入度为0节点的后缀节点files=umap[cur];for(int i=0;i<files.size();i++){inDegree[files[i]]-=1;if(inDegree[files[i]]==0)que.push(files[i]);}}if(res.size()==n){for(int i=0;i<n-1;i++){cout<<res[i]<<' ';}cout<<res[n-1]<<endl;}else cout<<-1<<endl;return 0;
}

47. 参加科学大会（第六期模拟笔试）

有向图中最短路径 dijkstra 算法朴素版

#include<iostream>
#include<vector>
#include<climits>
using namespace std;
//有向图中求最短路径。三部曲做题法
//数据的存储：二维数组存有向边及权值；visited数组；minDist数组:(保存各节点到源点的最短距离)
//第一步：寻找距离源点最近的节点
//第二步：更新节点为已访问
//第三步：更新未访问节点到源点的最短距离
int main(){//输入数据int n,m,s,e,v;cin>>n>>m;vector<vector<int>>grid(n+1,vector<int>(n+1,INT_MAX));for(int i=1;i<=m;i++){cin>>s>>e>>v;grid[s][e]=v;}vector<bool>visited(n+1,false);//标记节点是否被访问vector<int>minDist(n+1,INT_MAX);////处理数据//需要循环处理三步曲n次，minDist[1]=0;for(int i=1;i<=n;i++){//第一步int cur=1;int minval=INT_MAX;for(int j=1;j<=n;j++){if(!visited[j]&&minDist[j]<minval){minval=minDist[j];cur=j;}}//第二步visited[cur]=true;//第三步//只需要更新cur连接的节点即可for(int j=1;j<=n;j++){if(!visited[j]&&grid[cur][j]!=INT_MAX&&minDist[cur]+grid[cur][j]<minDist[j]){minDist[j]=minDist[cur]+grid[cur][j];                }}}//输出数据if(minDist[n]==INT_MAX) {cout<<-1<<endl;}else {cout<<minDist[n]<<endl;}return 0;
}

47. 参加科学大会（第六期模拟笔试）

有向图中最短路径 dijkstra 算法堆优化版

#include<iostream>
#include<vector>
#include<queue>
#include<climits>
#include<list>
using namespace std;
//该方法也符合三部曲，朴素版是通过遍历n次（节点个数）三部曲，每次将一个节点加入集合中
//堆优化版是用小顶堆对边进行排序，每次选择最短的边，和kruskal思想相似
//数据准备：visited数组,minDist数组，grid数组+邻接表，优先队列
//第一步：取出小顶堆堆顶数据，（堆自动排序了）
//第二步：标记节点已访问
//第三步：更新cur节点链接的节点到源点的最短距离，加入优先队列中//构造一个结构体表示邻接表
struct Edge{int to;//临间顶点int val;//边的权重Edge(int t,int w):to(t),val(w){}//构造函数
};
//小顶堆
class mycomparison{
public:
//操作符重载函数bool operator()(const pair<int,int>& lhs,const pair<int,int>& rhs){return lhs.second>rhs.second;//注意是大于，我也不知道为啥}    
};int main(){//输入数据int n,m,s,e,v;cin>>n>>m;vector<list<Edge>>grid(n+1);for(int i=0;i<m;i++){cin>>s>>e>>v;grid[s].push_back(Edge(e,v));}vector<bool>visited(n+1,false);vector<int>minDist(n+1,INT_MAX);//pair<int,int> 表示<节点，节点到源点的权值>priority_queue<pair<int,int>,vector<pair<int,int>>,mycomparison> pq;//处理数据pq.push(pair<int,int>(1,0));minDist[1]=0;//在队列不为空条件下进行三部曲的重复while(!pq.empty()){//第一步pair<int,int>cur=pq.top();pq.pop();//第二步visited[cur.first]=true;//第三步for(Edge edge:grid[cur.first]){if(!visited[edge.to]&&minDist[cur.first]+edge.val<minDist[edge.to]){minDist[edge.to]=minDist[cur.first]+edge.val;pq.push(pair<int,int>(edge.to,minDist[edge.to]));}}}if(minDist[n]==INT_MAX) cout<<-1<<endl;else cout<<minDist[n]<<endl;
}

dijkstra算法 不能用于权值有负数的情况

94. 城市间货物运输 I

Bellman_ford 算法

#include<iostream>
#include<vector>
#include<climits>
using namespace std;
//对于权值有负值的求单项图的最短路径问题
//松弛n-1次（n个节点）
//每次松弛遍历单向边，更新终点到源点的最短距离
int main(){//输入数据int n,m,s,t,v;cin>>n>>m;vector<vector<int>>grid;for(int i=0;i<m;i++){cin>>s>>t>>v;grid.push_back({s,t,v});}//处理数据vector<int>minDist(n+1,INT_MAX);minDist[1]=0;for(int i=1;i<n;i++){for(vector<int> &vec:grid){//加&可以避免循环时复制vector数组而产生的时间和空间开销int from=vec[0];int to=vec[1];int val=vec[2];if(minDist[from]!=INT_MAX&&minDist[to]>minDist[from]+val){minDist[to]=minDist[from]+val;}}}if(minDist[n]==INT_MAX) cout<<"unconnected"<<endl;else cout<<minDist[n]<<endl;return 0;
}

Bellman_ford 算法优化版本

#include<iostream>
#include<vector>
#include<list>
#include<climits>
#include<queue>
using namespace std;
//对bellman_ford 算法 进行优化，
//使用isInQueue数组，queue队列，减少无效次数的松弛
//构建结构体
struct Edge{int to;int val;Edge(int k,int w):to(k),val(w){}//构造函数
};
int main(){//输入数据int n,m,s,t,v;cin>>n>>m;vector<list<Edge>>grid(n+1);for(int i=0;i<m;i++){cin>>s>>t>>v;grid[s].push_back(Edge(t,v));}//处理数据vector<int>minDist(n+1,INT_MAX);vector<bool>isInQueue(n+1,false);minDist[1]=0;queue<int>que;que.push(1);isInQueue[1]=true;//进行松弛while(!que.empty()){int node=que.front();que.pop();isInQueue[node]=false;for(Edge &edge:grid[node]){int from=node;int to=edge.to;int val=edge.val;if(minDist[from]!=INT_MAX&&minDist[to]>minDist[from]+val){minDist[to]=minDist[from]+val;if(!isInQueue[to]) {que.push(to);isInQueue[to]=true;}}}}if(minDist[n]==INT_MAX) cout<<"unconnected"<<endl;else cout<<minDist[n]<<endl;return 0;
}

95. 城市间货物运输 II

#include<iostream>
#include<vector>
#include<climits>
using namespace std;
//本题存在负权回路的情况，正常只需要松弛n-1次就可以找到所有节点到源点的最短距离
//那么再多松弛一次，看minDist数组是否变化，有变化则存在负权回路
int main(){//输入数据int n,m,s,t,v;cin>>n>>m;vector<vector<int>>grid;for(int i=0;i<m;i++){cin>>s>>t>>v;grid.push_back({s,t,v});}//处理数据vector<int>minDist(n+1,INT_MAX);minDist[1]=0;bool fact=false;//进行n次松弛for(int i=1;i<=n;i++){for(vector<int>& vec:grid){int from=vec[0];int to=vec[1];int val=vec[2];if(i<n){if(minDist[from]!=INT_MAX&&minDist[to]>minDist[from]+val)minDist[to]=minDist[from]+val;}else {if(minDist[from]!=INT_MAX&&minDist[to]>minDist[from]+val)fact=true;}}}if(fact) cout<<"circle"<<endl;else {if(minDist[n]==INT_MAX) cout<<"unconnected"<<endl;else cout<<minDist[n]<<endl;}return 0;
}

SPFA法

#include<iostream>
#include<vector>
#include<list>
#include<climits>
#include<queue>
using namespace std;
//对bellman_ford 算法 进行优化，
//使用isInQueue数组，queue队列，减少无效次数的松弛
//构建结构体
struct Edge{int to;int val;Edge(int k,int w):to(k),val(w){}//构造函数
};
int main(){//输入数据int n,m,s,t,v;cin>>n>>m;vector<list<Edge>>grid(n+1);for(int i=0;i<m;i++){cin>>s>>t>>v;grid[s].push_back(Edge(t,v));}//处理数据vector<int>minDist(n+1,INT_MAX);vector<bool>isInQueue(n+1,false);vector<int>count(n+1,0);//记录节点加入队列的次数minDist[1]=0;queue<int>que;que.push(1);count[1]=1;bool fact=false;//进行松弛while(!que.empty()){int node=que.front();que.pop();for(Edge &edge:grid[node]){int from=node;int to=edge.to;int val=edge.val;if(minDist[from]!=INT_MAX&&minDist[to]>minDist[from]+val){minDist[to]=minDist[from]+val;if(!isInQueue[to]) {que.push(to);count[to]++;if(count[to]==n){fact=true;while(!que.empty())que.pop();break;}}}}}if(fact)cout<<"circle"<<endl;else if(minDist[n]==INT_MAX) cout<<"unconnected"<<endl;else cout<<minDist[n]<<endl;return 0;
}

96. 城市间货物运输 III

最多经过k个城市，从城市A到城市B的最短路径

#include<iostream>
#include<vector>
#include<climits>
using namespace std; 
//对所有边松弛n次，相当于计算起点到达与起点n条边相连的节点的最短距离
//最多经过k个城市,那么要到达与起点k+1个边相连的终点，松弛k+1次
//但是，要注意负权回路，更新minDist数组时，要看上一次松弛的from点的mindDise
int main(){//输入数据int n,m,s,t,v,src,dst,k;cin>>n>>m;vector<vector<int>>grid;for(int i=0;i<m;i++){cin>>s>>t>>v;grid.push_back({s,t,v});}cin>>src>>dst>>k;//处理数据vector<int>minDist(n+1,INT_MAX);vector<int>copy(n+1,INT_MAX);minDist[src]=0;//开始松弛for(int i=1;i<=k+1;i++){copy=minDist;for(vector<int>& vec:grid){int from=vec[0];int to=vec[1];int val=vec[2];if(copy[from]!=INT_MAX&&minDist[to]>copy[from]+val){minDist[to]=copy[from]+val;}}}if(minDist[dst]==INT_MAX) cout<<"unreachable"<<endl;else cout<<minDist[dst]<<endl;return 0;
}

97. 小明逛公园

Floyd算法

#include<iostream>
#include<vector>
using namespace std;int main(){//输入数据int n,m,u,v,w;cin>>n>>m;vector<vector<vector<int>>>dp(n+1,vector<vector<int>>(n+1,vector<int>(n+1,10005)));for(int i=0;i<m;i++){cin>>u>>v>>w;dp[u][v][0]=w;dp[v][u][0]=w;}//Floyd算法for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dp[i][j][k]=min(dp[i][j][k-1],dp[i][k][k-1]+dp[k][j][k-1]);}}}int q,start,end;cin>>q;while(q--){cin>>start>>end;if(dp[start][end][n]==10005) cout<<-1<<endl;else cout<<dp[start][end][n]<<endl;}return 0;
}

127. 骑士的攻击

#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;//A*算法   实际上是光搜的改良版
//光搜便利了太多多余的节点,可以加入一个启发式函数，引导算法向目标位置遍历
//通过对队列中的节点进行排序，让离目标最近的先出来。
//F=G+H。F是从起点到终点需要的距离。G是从起点到目前所遍历的节点经过的距离
//H是从目前节点到终点所需要的距离
//计算距离使用欧拉距离公式d=sqrt((x1-x2)^2+(y1-y2)^2)
int dir[8][2]={-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1};
int b1,b2;
int moves[1001][1001];//棋盘，同时记录路径长度struct Knight{int x,y;int g,h,f;bool operator <(const Knight & k) const {return k.f<f;}
};int Heuristic(const Knight &k){return (k.x-b1)*(k.x-b1)+(k.y-b2)*(k.y-b2);
}
priority_queue<Knight>que;
void astart(const Knight &k){Knight cur,next;que.push(k);while(!que.empty()){cur=que.top();que.pop();if(cur.x==b1&&cur.y==b2) break;for(int i=0;i<8;i++){//向八个方向遍历next.x=cur.x+dir[i][0];next.y=cur.y+dir[i][1];//排除掉不符合规定的情况if(next.x<1||next.x>1000||next.y<1||next.y>1000) continue;if(!moves[next.x][next.y]){//更新路径长度moves[next.x][next.y]=moves[cur.x][cur.y]+1;//开始计算f,g,hnext.g=cur.g+5;//没有开根号，为了提高精度next.h=Heuristic(next);next.f=next.g+next.h;que.push(next);}}}
}int main(){int n,a1,a2;cin>>n;while(n--){cin>>a1>>a2>>b1>>b2;memset(moves,0,sizeof(moves));//设置一块内存的值,//sizeof获取字节数Knight start;start.x=a1;start.y=a2;start.g=0;start.h=Heuristic(start);start.f=start.g+start.h;astart(start);while(!que.empty()) que.pop();cout<<moves[b1][b2]<<endl;}return 0;
}