卡码网 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));//初始化map
while(!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再处理t
umap[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,h
next.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;
}