有哪些网站可以做任务,重庆企业网站营销设计,企业搜索平台,江阴哪家做网站便宜卡码网 98. 所有可达路径
使用邻接矩阵存储#xff1a;
#includeiostream
#includevector
using namespace std;vectorvectorintres;//收集符合条件的路径vectorintpath;//0节点到终点的路径//确定递归函数 参数和返回值void dfs(c…卡码网 98. 所有可达路径
使用邻接矩阵存储
#includeiostream
#includevector
using namespace std;vectorvectorintres;//收集符合条件的路径vectorintpath;//0节点到终点的路径//确定递归函数 参数和返回值void dfs(const vectorvectorint graph,int x,int n){//确定终止条件if(xn){res.push_back(path);return;}//确定单层递归逻辑for(int i1;in;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;//输入数据cinnm;vectorvectorintgraph(n1,vectorint(n1,0));while(m--){cinst;graph[s][t]1;}//遍历path.push_back(1);dfs(graph,1,n);//输出数据if(res.size()0)cout-1endl;for(const vectorint pa:res){for(int i0;ipa.size()-1;i){coutpa[i] ;}coutpa[pa.size()-1]endl;}return 0;
}
使用邻接表存储
#includeiostream
#includevector
#includelist
using namespace std;vectorvectorintres;//收集符合条件的路径vectorintpath;//0节点到终点的路径//确定递归函数 参数和返回值void dfs(const vectorlistint graph,int x,int n){//确定终止条件if(xn){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;//输入数据cinnm;vectorlistintgraph(n1);while(m--){cinst;graph[s].push_back(t);}//遍历path.push_back(1);dfs(graph,1,n);//输出数据if(res.size()0)cout-1endl;for(const vectorint pa:res){for(int i0;ipa.size()-1;i){coutpa[i] ;}coutpa[pa.size()-1]endl;}return 0;
}
卡码网 99. 岛屿数量
dfs搜索
#includeiostream
#includevector
using namespace std;int dir[4][2]{0,1,1,0,0,-1,-1,0};//右下左上 四个方向
//确定递归函数参数和返回值
void dfs(const vectorvectorint grid,vectorvectorbool visited,int x,int y){//确定终止条件//if(visited[x][y]true||grid[x][y]0)return;//不能加这个终止我在上一层已经把状态变为true我就是要遍历这个点的四周的你//给我终止了破坏了我的遍历//确定单层递归逻辑for(int i0;i4;i){int nextxxdir[i][0];int nextyydir[i][1];if(nextx0||nextxgrid.size()||nexty0||nextygrid[0].size())continue;if(grid[nextx][nexty]1visited[nextx][nexty]false){visited[nextx][nexty]true;dfs(grid,visited,nextx,nexty);//不需要回溯就是要dfs遍历一遍把周围的陆地都标记一下}}
}
int main(){//输入数据int n,m;cinnm;vectorvectorintgrid(n,vectorint(m,0));for(int x0;xn;x){for(int y0;ym;y){cingrid[x][y];}}vectorvectorboolvisited(n,vectorbool(m,false));//处理数据int res0;for(int i0;in;i){for(int j0;jm;j){if(grid[i][j]1visited[i][j]false){res;visited[i][j]true;dfs(grid,visited,i,j);}}}coutresendl;return 0;
}
bfs搜索
#includeiostream
#includevector
#includequeue
using namespace std;int dir[4][2]{0,1,1,0,0,-1,-1,0};//右下左上 四个方向//确定递归函数参数和返回值
void bfs(const vectorvectorint grid,vectorvectorbool visited,int x,int y){//确定终止条件//确定单层递归逻辑queuepairint,intque;que.push({x,y});visited[x][y]true;while(!que.empty()){pairint,intpaque.front();que.pop();int curxpa.first;int curypa.second;for(int i0;i4;i){int nextxcurxdir[i][0];int nextycurydir[i][1];if(nextx0||nextxgrid.size()||nexty0||nextygrid[0].size())continue;if(grid[nextx][nexty]1visited[nextx][nexty]false){que.push({nextx,nexty});visited[nextx][nexty]true;}}}}
int main(){//输入数据int n,m;cinnm;vectorvectorintgrid(n,vectorint(m,0));for(int x0;xn;x){for(int y0;ym;y){cingrid[x][y];}}vectorvectorboolvisited(n,vectorbool(m,false));//处理数据int res0;for(int i0;in;i){for(int j0;jm;j){if(grid[i][j]1visited[i][j]false){res;bfs(grid,visited,i,j);}}}coutresendl;return 0;
}
分析对于这道题dfs与bfs的做法dfs函数中还有对dfs函数本身的调用bfs函数中没有对bfs函数本身的调用bfs做法中对一个点进行bfs函数把这个点压入队列中让后从队列中取出点对点的四周进行遍历如果符合条件就把点压入队列中让后函数一直持续从队列中取数进行遍历直到队列中为空。
100. 岛屿的最大面积
dfs法一dfs函数处理下一个节点不需要再写终止条件因为终止条件包含在单层循环处理中
#includeiostream
#includevector
using namespace std;int dir[4][2]{0,1,1,0,0,-1,-1,0};
int count0;
//dfs处理下一个节点
//确定递归函数参数和返回值
void dfs(vectorvectorint grid,vectorvectorbool visited,int x,int y){for(int i0;i4;i){int nextxxdir[i][0];int nextyydir[i][1];if(nextx0||nextxgrid.size()||nexty0||nextygrid[0].size()) continue;if(visited[nextx][nexty]falsegrid[nextx][nexty]1){count;visited[nextx][nexty]true;dfs(grid,visited,nextx,nexty);}}
}int main(){//输入数据int res0;int n,m;cinnm;vectorvectorintgrid(n,vectorint(m,0));for(int i0;in;i){for(int j0;jm;j){cingrid[i][j];}}vectorvectorboolvisited(n,vectorbool(m,false));//处理数据for(int i0;in;i){for(int j0;jm;j){if(grid[i][j]1visited[i][j]false){count1;visited[i][j]true;dfs(grid,visited,i,j);resmax(count,res);}}}coutresendl;return 0;
}
dfs法二dfs处理当前节点需要写终止条件
#includeiostream
#includevector
using namespace std;int dir[4][2]{0,1,1,0,0,-1,-1,0};
int count0;
//dfs处理当前节点
//确定递归函数参数和返回值
void dfs(vectorvectorint grid,vectorvectorbool visited,int x,int y){//确定终止条件if(grid[x][y]0||visited[x][y]true) return;//确定单层递归逻辑count;visited[x][y]true;for(int i0;i4;i){int nextxxdir[i][0];int nextyydir[i][1];if(nextx0||nextxgrid.size()||nexty0||nextygrid[0].size()) continue;dfs(grid,visited,nextx,nexty);}
}int main(){//输入数据int res0;int n,m;cinnm;vectorvectorintgrid(n,vectorint(m,0));for(int i0;in;i){for(int j0;jm;j){cingrid[i][j];}}vectorvectorboolvisited(n,vectorbool(m,false));//处理数据for(int i0;in;i){for(int j0;jm;j){if(grid[i][j]1visited[i][j]false){count0;dfs(grid,visited,i,j);resmax(count,res);}}}coutresendl;return 0;
}
方法三bfs遍历
#includeiostream
#includevector
#includequeue
using namespace std;int dir[4][2]{0,1,1,0,0,-1,-1,0};
int count0;
//dfs处理当前节点
//确定递归函数参数和返回值
void bfs(vectorvectorint grid,vectorvectorbool visited,int x,int y){//确定单层递归逻辑queuepairint,intque;que.push({x,y});count;visited[x][y]true;while(!que.empty()){pairint,intpaque.front();que.pop();int xxpa.first;int yypa.second;for(int i0;i4;i){int nextxxxdir[i][0];int nextyyydir[i][1];if(nextx0||nextxgrid.size()||nexty0||nextygrid[0].size()) continue;if(grid[nextx][nexty]1visited[nextx][nexty]false){que.push({nextx,nexty});count;visited[nextx][nexty]true;}}}
}int main(){//输入数据int res0;int n,m;cinnm;vectorvectorintgrid(n,vectorint(m,0));for(int i0;in;i){for(int j0;jm;j){cingrid[i][j];}}vectorvectorboolvisited(n,vectorbool(m,false));//处理数据for(int i0;in;i){for(int j0;jm;j){if(grid[i][j]1visited[i][j]false){count0;bfs(grid,visited,i,j);resmax(count,res);}}}coutresendl;return 0;
}
101. 孤岛的总面积
用dfs遍历
#includeiostream
#includevector
using namespace std;
int dir[4][2]{0,1,1,0,0,-1,-1,0};
//确定递归函数参数和返回值
//该dfs是为了把靠边缘的岛屿变成海洋
void dfs(vectorvectorint grid,int x,int y){//确定单层递归逻辑grid[x][y]0;for(int i0;i4;i){int nextxxdir[i][0];int nextyydir[i][1];if(nextx0||nextxgrid.size()||nexty0||nextygrid[0].size()){continue;}if(grid[nextx][nexty]0) continue;dfs(grid,nextx,nexty);}}
int main(){//输入数据int n,m;cinnm;vectorvectorintgrid(n,vectorint(m,0));for(int i0;in;i){for(int j0;jm;j){cingrid[i][j];}}//处理数据//遍历挨着边缘的岛屿for(int i0;in;i){if(grid[i][0]1) dfs(grid,i,0);if(grid[i][m-1]1) dfs(grid,i,m-1);}for(int j0;jm;j){if(grid[0][j]1) dfs(grid,0,j);if(grid[n-1][j]1) dfs(grid,n-1,j);}int res0;for(int i0;in;i){for(int j0;jm;j){if(grid[i][j]1)res;}}coutresendl;return 0;
}
使用bfs遍历
#includeiostream
#includevector
#includequeue
using namespace std;
int dir[4][2]{0,1,1,0,0,-1,-1,0};
//确定递归函数参数和返回值
//该bfs是为了把靠边缘的岛屿变成海洋
void bfs(vectorvectorint grid,int x,int y){//确定单层递归逻辑grid[x][y]0;queuepairint,intque;que.push({x,y});while(!que.empty()){pairint,intpa;paque.front();que.pop();int xxpa.first;int yypa.second;for(int i0;i4;i){int nextxxxdir[i][0];int nextyyydir[i][1];if(nextx0||nextxgrid.size()||nexty0||nextygrid[0].size()){continue;}if(grid[nextx][nexty]0) continue;que.push({nextx,nexty});grid[nextx][nexty]0;}}}
int main(){//输入数据int n,m;cinnm;vectorvectorintgrid(n,vectorint(m,0));for(int i0;in;i){for(int j0;jm;j){cingrid[i][j];}}//处理数据//遍历挨着边缘的岛屿for(int i0;in;i){if(grid[i][0]1) bfs(grid,i,0);if(grid[i][m-1]1) bfs(grid,i,m-1);}for(int j0;jm;j){if(grid[0][j]1) bfs(grid,0,j);if(grid[n-1][j]1) bfs(grid,n-1,j);}int res0;for(int i0;in;i){for(int j0;jm;j){if(grid[i][j]1)res;}}coutresendl;return 0;
}
102. 沉没孤岛
使用dfs遍历
#includeiostream
#includevector
using namespace std;
int dir[4][2]{0,1,1,0,0,-1,-1,0};
//确定递归函数参数和返回值
//该dfs是为了把靠边缘的岛屿用2标记让后主函数中再遍历把2变成1,1变成0
void dfs(vectorvectorint grid,int x,int y){//确定单层递归逻辑grid[x][y]2;for(int i0;i4;i){int nextxxdir[i][0];int nextyydir[i][1];if(nextx0||nextxgrid.size()||nexty0||nextygrid[0].size()){continue;}if(grid[nextx][nexty]0||grid[nextx][nexty]2) continue;dfs(grid,nextx,nexty);}}
int main(){//输入数据int n,m;cinnm;vectorvectorintgrid(n,vectorint(m,0));for(int i0;in;i){for(int j0;jm;j){cingrid[i][j];}}//处理数据//遍历挨着边缘的岛屿for(int i0;in;i){if(grid[i][0]1) dfs(grid,i,0);if(grid[i][m-1]1) dfs(grid,i,m-1);}for(int j0;jm;j){if(grid[0][j]1) dfs(grid,0,j);if(grid[n-1][j]1) dfs(grid,n-1,j);}for(int i0;in;i){for(int j0;jm;j){if(grid[i][j]1) grid[i][j]0;if(grid[i][j]2) grid[i][j]1;}}for(int i0;in;i){for(int j0;jm;j){coutgrid[i][j] ;}coutendl;}return 0;
}
使用bfs遍历
#includeiostream
#includevector
#includequeue
using namespace std;
int dir[4][2]{0,1,1,0,0,-1,-1,0};
//确定递归函数参数和返回值
//该bfs是为了把靠边缘的岛屿用2标记让后主函数中再遍历把2变成1,1变成0
void bfs(vectorvectorint grid,int x,int y){//确定单层递归逻辑grid[x][y]2;queuepairint,intque;que.push({x,y});while(!que.empty()){pairint,intpa;paque.front();que.pop();int xxpa.first;int yypa.second;for(int i0;i4;i){int nextxxxdir[i][0];int nextyyydir[i][1];if(nextx0||nextxgrid.size()||nexty0||nextygrid[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;cinnm;vectorvectorintgrid(n,vectorint(m,0));for(int i0;in;i){for(int j0;jm;j){cingrid[i][j];}}//处理数据//遍历挨着边缘的岛屿for(int i0;in;i){if(grid[i][0]1) bfs(grid,i,0);if(grid[i][m-1]1) bfs(grid,i,m-1);}for(int j0;jm;j){if(grid[0][j]1) bfs(grid,0,j);if(grid[n-1][j]1) bfs(grid,n-1,j);}for(int i0;in;i){for(int j0;jm;j){if(grid[i][j]1)grid[i][j]0;if(grid[i][j]2) grid[i][j]1;}}for(int i0;in;i){for(int j0;jm;j){coutgrid[i][j] ;}coutendl;}return 0;
}
103. 水流问题
#includeiostream
#includevector
using namespace std;int dir[4][2]{0,1,1,0,0,-1,-1,0};//确定递归函数 参数
//该dfs遍历是对当前节点进行处理。从边缘逆流遍历标记能到达边缘的坐标
void dfs(vectorvectorint grid,vectorvectorbool visited,int x,int y){//确定终止条件if(visited[x][y]true) return;//确定单层递归逻辑visited[x][y]true;for(int i0;i4;i){int nextxxdir[i][0];int nextyydir[i][1];if(nextx0||nextxgrid.size()||nexty0||nextygrid[0].size()){continue;}if(grid[x][y]grid[nextx][nexty]) continue;dfs(grid,visited,nextx,nexty);}
}int main(){//输入数据int n,m;cinnm;vectorvectorintgrid(n,vectorint(m,0));for(int i0;in;i){for(int j0;jm;j){cingrid[i][j];}}//处理数据vectorvectorboolfirstBorder(n,vectorbool(m,false));vectorvectorboolsecondBorder(n,vectorbool(m,false));//从边缘进行dfs遍历标记目的单元格for(int i0;in;i){dfs(grid,firstBorder,i,0);//左侧dfs(grid,secondBorder,i,m-1);//右侧}for(int j0;jm;j){dfs(grid,firstBorder,0,j);//上侧dfs(grid,secondBorder,n-1,j);//下侧}for(int i0;in;i){for(int j0;jm;j){if(firstBorder[i][j]secondBorder[i][j]) couti jendl;}}return 0;
}
104. 建造最大岛屿
#includeiostream
#includevector
#includeunordered_map
#includeunordered_set
using namespace std;
int dir[4][2]{0,1,1,0,-1,0,0,-1};
int count;
//确定递归函数参数
//该dfs是将每个岛屿染成不同的颜色并计算每个岛屿的面积大小
void dfs(vectorvectorint grid,vectorvectorbool 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 i0;i4;i){int nextxxdir[i][0];int nextyydir[i][1];if(nextx0||nextxgrid.size()||nexty0||nextygrid[0].size()) continue;dfs(grid,visited,nextx,nexty,mark);}
}int main(){//输入数据int n,m;cinnm;vectorvectorintgrid(n,vectorint(m,0));for(int i0;in;i){for(int j0;jm;j){cingrid[i][j];}}vectorvectorboolvisited(n,vectorbool(m,false));//处理数据unordered_mapint,int gridNum;//记录每个岛屿的面积int mark2;//记录每个岛屿的编号bool isAllGridtrue;//标记是否整个地图都是陆地for(int i0;in;i){for(int j0;jm;j){if(grid[i][j]0)isAllGridfalse;if(visited[i][j]falsegrid[i][j]1){count0;dfs(grid,visited,i,j,mark);gridNum[mark]count;mark;}}}if(isAllGrid){coutn*mendl;return 0;}//根据添加陆地的位置计算周边岛屿面积之和int res0;//记录最后结果unordered_setintvisitedGrid;//标记访问过的岛屿for(int i0;in;i){for(int j0;jm;j){count1;//记录连接之后的岛屿数量visitedGrid.clear();//每次使用时清空if(grid[i][j]0){for(int k0;k4;k){int nearxidir[k][0];int nearyjdir[k][1];if(nearx0||nearxgrid.size()||neary0||nearygrid[0].size()){continue;}if(visitedGrid.count(grid[nearx][neary]))continue;//添加过的岛屿不要重复添加countgridNum[grid[nearx][neary]];visitedGrid.insert(grid[nearx][neary]);}}resmax(res,count);}}coutresendl;return 0;
}
思路真的感觉很难想而且代码很难实现。不过这道题应该还是要练图论的遍历用的dfs遍历感觉对图论的遍历更加掌握了。
110. 字符串接龙
#includeiostream
#includevector
#includeunordered_set
#includeunordered_map
#includequeue
#includestring
using namespace std;
int main(){//输入数据int n;cinn;string str,beginStr,endStr;cinbeginStrendStr;unordered_setstring strSet;for(int i0;in;i){cinstr;strSet.insert(str);}//处理数据//转换的字符串之间只相差一个字符字符串之间的连接形成了一个无向图//遍历无向图找到最短路径使用广搜。//尝试替换每一个字符如果在set字典中找到并且没有没遍历过//就可以加入que中加入map中保存queuestringque;que.push(beginStr);//初始化队列unordered_mapstring,intstrMap;//map用来记录遍历长度验证是否遍历过strMap.insert(pairstring,int(beginStr,1));//初始化mapwhile(!que.empty()){string wordque.front();que.pop();int pathstrMap[word];//轮流替换每个字符for(int i0;iword.size();i){string newwordword;//不能在原本的字符上直接替换//尝试替换26个字符for(int j0;j26;j){newword[i]ja;if(newwordendStr){coutpath1endl;return 0;}if(strSet.find(newword)!strSet.end()strMap.find(newword)strMap.end()){que.push(newword);strMap.insert(pairstring,int(newword,path1));}}}}cout0endl;//没找到
}
105. 有向图的完全可达性
#includeiostream
#includelist
#includevector
using namespace std;//确定递归函数参数 使用dfs遍历
void dfs(const vectorlistint grid,vectorbool visited,int key){//dfs处理当前节点if(visited[key]) return;//确定单层递归逻辑visited[key]true;listintkeysgrid[key];for(int key : keys){dfs(grid,visited,key);}
}int main(){//输入数据int n,k,s,t;cinnk;//使用邻接表保存图vectorlistint grid(n1);while(k--){cinst;grid[s].push_back(t);}//处理数据vectorbool visited(n1,false);dfs(grid,visited,1);for(int i1;in;i){if(visited[i]false) {cout-1endl;return 0;}}cout1endl;return 0;
}
dfs遍历 细微差别
#includeiostream
#includelist
#includevector
using namespace std;//确定递归函数参数 使用dfs遍历
void dfs(const vectorlistint grid,vectorbool visited,int key){//dfs处理下一个节点//确定单层递归逻辑listintkeysgrid[key];for(int key : keys){if(visited[key])continue;visited[key]true;dfs(grid,visited,key);}
}int main(){//输入数据int n,k,s,t;cinnk;//使用邻接表保存图vectorlistint grid(n1);while(k--){cinst;grid[s].push_back(t);}//处理数据vectorbool visited(n1,false);visited[1]true;dfs(grid,visited,1);for(int i1;in;i){if(visited[i]false) {cout-1endl;return 0;}}cout1endl;return 0;
}
通过bfs遍历
#includeiostream
#includelist
#includevector
#includequeue
using namespace std;//确定递归函数参数 使用bfs遍历
void bfs(const vectorlistint grid,vectorbool visited,int key){//确定单层递归逻辑queueintque;que.push(key);while(!que.empty()){int curque.front();que.pop();listintkeysgrid[cur];for(int key:keys){if(visited[key]) continue;visited[key]true;que.push(key);}}
}int main(){//输入数据int n,k,s,t;cinnk;//使用邻接表保存图vectorlistint grid(n1);while(k--){cinst;grid[s].push_back(t);}//处理数据vectorbool visited(n1,false);visited[1]true;bfs(grid,visited,1);for(int i1;in;i){if(visited[i]false) {cout-1endl;return 0;}}cout1endl;return 0;
}
106. 岛屿的周长
#includeiostream
#includevector
using namespace std;
int dir[4][2]{0,1,1,0,-1,0,0,-1};
int main(){int n,m;cinnm;vectorvectorintgrid(n,vectorint(m,0));for(int i0;in;i){for(int j0;jm;j){cingrid[i][j];}}int res0;for(int i0;in;i){for(int j0;jm;j){if(grid[i][j]1){for(int k0;k4;k){int xidir[k][0];int yjdir[k][1];if(x0||xn||y0||ym||grid[x][y]0)res;}}}}coutresendl;return 0;
}107. 寻找存在的路径
#includeiostream
#includevector
using namespace std;
//确定节点数量
int n105;
//根节点数组
vectorintfather(n,0);
//并查集初始化
void init(){for(int i0;in;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){ufind(u);vfind(v);return uv;
}
//将v-u加入到并查集中
void ioin(int u,int v){ufind(u);vfind(v);if(uv) return ;father[v]u;
}
int main(){int m,s,t,source,destination;cinnm;init();for(int i0;im;i){cinst;ioin(s,t);}cinsourcedestination;if(isSame(source,destination))cout1endl;else cout0endl;return 0;
}
108. 冗余连接
#includeiostream
#includevector
using namespace std;
//确定节点个数
int n1005;
vectorintfather(n,0);
//初始化并查集
void init(){for(int i0;in;i){father[i]i;}
}
//并查集中寻根
int find(int u){return ufather[u]?u:father[u]find(father[u]);
}
//判断是否在一个集合里
bool isSame(int u,int v){ufind(u);vfind(v);return uv;
}
//将v-u加入到并查集中
void join(int u,int v){ufind(u);vfind(v);if(uv)return;father[v]u;
}
int main(){int s,t;cinn;init();for(int i0;in;i){cinst;if(isSame(s,t)){couts tendl;return 0;}else join(s,t);}
}
109. 冗余连接II
#includeiostream
#includevector
using namespace std;int n1005;
vectorintfather(n,0);
//并查集初始化
void init(){for(int i0;in;i){father[i]i;}
}
//并查集中查根
int find(int u){return ufather[u]?u:father[u]find(father[u]);
}
//判断并查集中是否同根
bool isSame(int u,int v){ufind(u);vfind(v);return uv;
}
//将v-u加入并查集中
void join(int u,int v){ufind(u);vfind(v);if(uv)return;father[v]u;
}
bool isTreeAfterRemoveEdge(vectorvectorint edges,int deleedge){//删除某边利用并查集看是否构成有向树。或者删除另一条边。init();for(int i0;in;i){if(ideleedge) continue;if(isSame(edges[i][0],edges[i][1])){return false;}join(edges[i][0],edges[i][1]);}return true;}
void getRemoveEdge(vectorvectorint edges){//依次将各个边加入并查集中同时看是否构成环init();for(int i0;in;i){if(isSame(edges[i][0],edges[i][1])) {coutedges[i][0] edges[i][1]endl;return;}join(edges[i][0],edges[i][1]);}}
int main(){//输入数据int s,t;cinn;vectorvectorintedges;//保存有向边vectorintinDegree(n,0);for(int i0;in;i){cinst;inDegree[t];//入度加一edges.push_back({s,t});}//处理数据 考虑三种情况//寻找有没有入度为2的如果有找到对应的两条边删除某边利用isTreeAfterRemoveEdge函数//为了保证最先删除的是最后输入的边将两条边提取出来按一定顺序尝试删除//情况三入度没有2的则是构成了单向环利用getMoveEdge函数vectorintvec;//记录指向入度为2的点//寻找度为2的for(int in-1;i0;i--){if(inDegree[edges[i][1]]2){vec.push_back(i);}}//情况一,二if(vec.size()2){if(isTreeAfterRemoveEdge(edges,vec[0])){coutedges[vec[0]][0] edges[vec[0]][1]endl;}else coutedges[vec[1]][0] edges[vec[1]][1]endl;return 0;}//情况三getRemoveEdge(edges);}
53. 寻宝第七期模拟笔试
最小生成树 prim算法
#includeiostream
#includevector
#includeclimits
using namespace std;int main(){int v,e,s,p,t;cinve;vectorvectorintgrid(v1,vectorint(v1,10001));//存储图for(int i1;ie;i){cinspt;grid[s][p]t;grid[p][s]t;//存储边及权值}vectorboolisIntree(v1,false);//是否在树里//所有节点到最小生成树的最小距离vectorintminDist(v1,10001);//需要执行n-1次三部曲将边加入到最小生成树中for(int i1;iv;i){int cur-1;//要加入最小生成树的节点int minValINT_MAX;//非最小生成树节点到树的最短距离//prim第一步 选距离最小生成树最近的节点//条件1.不在最小生成树里//2.距离最小生成树最近的节点for(int j1;jv;j){if(!isIntree[j]minDist[j]minVal){curj;minValminDist[j];}}//prim第二步 节点加入树isIntree[cur]true;//rim第三步 更新非树节点到树的最小距离//只需要更新与新添加到树中节点相关的节点for(int j1;jv;j){if(!isIntree[j]grid[cur][j]minDist[j]){minDist[j]grid[cur][j];}}}int res0;for(int i2;iv;i){resminDist[i];}coutresendl;return 0;
}
53. 寻宝第七期模拟笔试
最小生成树 kruskal算法
#includeiostream
#includevector
#includealgorithm
using namespace std;int n10001;//节点数量
vectorint father(n,0);
//初始化并查集
void init(){for(int i1;in;i){father[i]i;}
}
//在并查集中查找根
int find(int u){return ufather[u]?u:father[u]find(father[u]);
}
//判断是否在同一集合中
bool isSame(int u,int v){ufind(u);vfind(v);return uv;
}
//将v-u加入到并查集中
void join(int u,int v){ufind(u);vfind(v);if(uv)return;father[v]u;
}struct edge{int l,r,val;
};
int main(){//输入数据int v,e,r,s,t;cinve;vectoredgeedges(e1);for(int i1;ie;i){cinrst;edges.push_back({r,s,t});}//处理数据 //为edges排序接着遍历如果不构成环就把边加入到并查集中//同时累加权值int res_val0;init();sort(edges.begin(),edges.end(),[](const edge a,const edge b){return a.valb.val;});for(edge eg:edges){int ifind(eg.l);int jfind(eg.r);if(i!j){res_valeg.val;join(i,j);}}coutres_valendl;return 0;
}
117. 软件构建
#includeiostream
#includevector
#includeunordered_map
#includequeue
using namespace std;int main(){//输入数据int n,m,s,t;cinnm;unordered_mapint,vectorintumap(n);//记录文件间依赖关系vectorintinDegree(n,0);for(int i0;im;i){cinst;//先处理s再处理tumap[s].push_back(t);inDegree[t];//t的入度1}//处理数据//1.找到入度为0的点2.让其后缀节点入度减一。重复这两点queueintque;for(int i0;in;i){if(inDegree[i]0) que.push(i);}vectorintres;//记录处理顺序结果while(!que.empty()){int curque.front();que.pop();res.push_back(cur);vectorintfiles;//保存入度为0节点的后缀节点filesumap[cur];for(int i0;ifiles.size();i){inDegree[files[i]]-1;if(inDegree[files[i]]0)que.push(files[i]);}}if(res.size()n){for(int i0;in-1;i){coutres[i] ;}coutres[n-1]endl;}else cout-1endl;return 0;
}
47. 参加科学大会第六期模拟笔试
有向图中最短路径 dijkstra 算法朴素版
#includeiostream
#includevector
#includeclimits
using namespace std;
//有向图中求最短路径。三部曲做题法
//数据的存储二维数组存有向边及权值visited数组minDist数组:(保存各节点到源点的最短距离)
//第一步寻找距离源点最近的节点
//第二步更新节点为已访问
//第三步更新未访问节点到源点的最短距离
int main(){//输入数据int n,m,s,e,v;cinnm;vectorvectorintgrid(n1,vectorint(n1,INT_MAX));for(int i1;im;i){cinsev;grid[s][e]v;}vectorboolvisited(n1,false);//标记节点是否被访问vectorintminDist(n1,INT_MAX);////处理数据//需要循环处理三步曲n次minDist[1]0;for(int i1;in;i){//第一步int cur1;int minvalINT_MAX;for(int j1;jn;j){if(!visited[j]minDist[j]minval){minvalminDist[j];curj;}}//第二步visited[cur]true;//第三步//只需要更新cur连接的节点即可for(int j1;jn;j){if(!visited[j]grid[cur][j]!INT_MAXminDist[cur]grid[cur][j]minDist[j]){minDist[j]minDist[cur]grid[cur][j]; }}}//输出数据if(minDist[n]INT_MAX) {cout-1endl;}else {coutminDist[n]endl;}return 0;
}
47. 参加科学大会第六期模拟笔试
有向图中最短路径 dijkstra 算法堆优化版
#includeiostream
#includevector
#includequeue
#includeclimits
#includelist
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 pairint,int lhs,const pairint,int rhs){return lhs.secondrhs.second;//注意是大于我也不知道为啥}
};int main(){//输入数据int n,m,s,e,v;cinnm;vectorlistEdgegrid(n1);for(int i0;im;i){cinsev;grid[s].push_back(Edge(e,v));}vectorboolvisited(n1,false);vectorintminDist(n1,INT_MAX);//pairint,int 表示节点节点到源点的权值priority_queuepairint,int,vectorpairint,int,mycomparison pq;//处理数据pq.push(pairint,int(1,0));minDist[1]0;//在队列不为空条件下进行三部曲的重复while(!pq.empty()){//第一步pairint,intcurpq.top();pq.pop();//第二步visited[cur.first]true;//第三步for(Edge edge:grid[cur.first]){if(!visited[edge.to]minDist[cur.first]edge.valminDist[edge.to]){minDist[edge.to]minDist[cur.first]edge.val;pq.push(pairint,int(edge.to,minDist[edge.to]));}}}if(minDist[n]INT_MAX) cout-1endl;else coutminDist[n]endl;
}
dijkstra算法 不能用于权值有负数的情况
94. 城市间货物运输 I
Bellman_ford 算法
#includeiostream
#includevector
#includeclimits
using namespace std;
//对于权值有负值的求单项图的最短路径问题
//松弛n-1次n个节点
//每次松弛遍历单向边更新终点到源点的最短距离
int main(){//输入数据int n,m,s,t,v;cinnm;vectorvectorintgrid;for(int i0;im;i){cinstv;grid.push_back({s,t,v});}//处理数据vectorintminDist(n1,INT_MAX);minDist[1]0;for(int i1;in;i){for(vectorint vec:grid){//加可以避免循环时复制vector数组而产生的时间和空间开销int fromvec[0];int tovec[1];int valvec[2];if(minDist[from]!INT_MAXminDist[to]minDist[from]val){minDist[to]minDist[from]val;}}}if(minDist[n]INT_MAX) coutunconnectedendl;else coutminDist[n]endl;return 0;
}
Bellman_ford 算法优化版本
#includeiostream
#includevector
#includelist
#includeclimits
#includequeue
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;cinnm;vectorlistEdgegrid(n1);for(int i0;im;i){cinstv;grid[s].push_back(Edge(t,v));}//处理数据vectorintminDist(n1,INT_MAX);vectorboolisInQueue(n1,false);minDist[1]0;queueintque;que.push(1);isInQueue[1]true;//进行松弛while(!que.empty()){int nodeque.front();que.pop();isInQueue[node]false;for(Edge edge:grid[node]){int fromnode;int toedge.to;int valedge.val;if(minDist[from]!INT_MAXminDist[to]minDist[from]val){minDist[to]minDist[from]val;if(!isInQueue[to]) {que.push(to);isInQueue[to]true;}}}}if(minDist[n]INT_MAX) coutunconnectedendl;else coutminDist[n]endl;return 0;
}
95. 城市间货物运输 II
#includeiostream
#includevector
#includeclimits
using namespace std;
//本题存在负权回路的情况正常只需要松弛n-1次就可以找到所有节点到源点的最短距离
//那么再多松弛一次看minDist数组是否变化有变化则存在负权回路
int main(){//输入数据int n,m,s,t,v;cinnm;vectorvectorintgrid;for(int i0;im;i){cinstv;grid.push_back({s,t,v});}//处理数据vectorintminDist(n1,INT_MAX);minDist[1]0;bool factfalse;//进行n次松弛for(int i1;in;i){for(vectorint vec:grid){int fromvec[0];int tovec[1];int valvec[2];if(in){if(minDist[from]!INT_MAXminDist[to]minDist[from]val)minDist[to]minDist[from]val;}else {if(minDist[from]!INT_MAXminDist[to]minDist[from]val)facttrue;}}}if(fact) coutcircleendl;else {if(minDist[n]INT_MAX) coutunconnectedendl;else coutminDist[n]endl;}return 0;
}
SPFA法
#includeiostream
#includevector
#includelist
#includeclimits
#includequeue
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;cinnm;vectorlistEdgegrid(n1);for(int i0;im;i){cinstv;grid[s].push_back(Edge(t,v));}//处理数据vectorintminDist(n1,INT_MAX);vectorboolisInQueue(n1,false);vectorintcount(n1,0);//记录节点加入队列的次数minDist[1]0;queueintque;que.push(1);count[1]1;bool factfalse;//进行松弛while(!que.empty()){int nodeque.front();que.pop();for(Edge edge:grid[node]){int fromnode;int toedge.to;int valedge.val;if(minDist[from]!INT_MAXminDist[to]minDist[from]val){minDist[to]minDist[from]val;if(!isInQueue[to]) {que.push(to);count[to];if(count[to]n){facttrue;while(!que.empty())que.pop();break;}}}}}if(fact)coutcircleendl;else if(minDist[n]INT_MAX) coutunconnectedendl;else coutminDist[n]endl;return 0;
}
96. 城市间货物运输 III
最多经过k个城市从城市A到城市B的最短路径
#includeiostream
#includevector
#includeclimits
using namespace std;
//对所有边松弛n次相当于计算起点到达与起点n条边相连的节点的最短距离
//最多经过k个城市,那么要到达与起点k1个边相连的终点松弛k1次
//但是要注意负权回路更新minDist数组时要看上一次松弛的from点的mindDise
int main(){//输入数据int n,m,s,t,v,src,dst,k;cinnm;vectorvectorintgrid;for(int i0;im;i){cinstv;grid.push_back({s,t,v});}cinsrcdstk;//处理数据vectorintminDist(n1,INT_MAX);vectorintcopy(n1,INT_MAX);minDist[src]0;//开始松弛for(int i1;ik1;i){copyminDist;for(vectorint vec:grid){int fromvec[0];int tovec[1];int valvec[2];if(copy[from]!INT_MAXminDist[to]copy[from]val){minDist[to]copy[from]val;}}}if(minDist[dst]INT_MAX) coutunreachableendl;else coutminDist[dst]endl;return 0;
}
97. 小明逛公园
Floyd算法
#includeiostream
#includevector
using namespace std;int main(){//输入数据int n,m,u,v,w;cinnm;vectorvectorvectorintdp(n1,vectorvectorint(n1,vectorint(n1,10005)));for(int i0;im;i){cinuvw;dp[u][v][0]w;dp[v][u][0]w;}//Floyd算法for(int k1;kn;k){for(int i1;in;i){for(int j1;jn;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;cinq;while(q--){cinstartend;if(dp[start][end][n]10005) cout-1endl;else coutdp[start][end][n]endl;}return 0;
}
127. 骑士的攻击
#includeiostream
#includevector
#includequeue
#includestring.h
using namespace std;//A*算法 实际上是光搜的改良版
//光搜便利了太多多余的节点,可以加入一个启发式函数引导算法向目标位置遍历
//通过对队列中的节点进行排序让离目标最近的先出来。
//FGH。F是从起点到终点需要的距离。G是从起点到目前所遍历的节点经过的距离
//H是从目前节点到终点所需要的距离
//计算距离使用欧拉距离公式dsqrt((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.ff;}
};int Heuristic(const Knight k){return (k.x-b1)*(k.x-b1)(k.y-b2)*(k.y-b2);
}
priority_queueKnightque;
void astart(const Knight k){Knight cur,next;que.push(k);while(!que.empty()){curque.top();que.pop();if(cur.xb1cur.yb2) break;for(int i0;i8;i){//向八个方向遍历next.xcur.xdir[i][0];next.ycur.ydir[i][1];//排除掉不符合规定的情况if(next.x1||next.x1000||next.y1||next.y1000) continue;if(!moves[next.x][next.y]){//更新路径长度moves[next.x][next.y]moves[cur.x][cur.y]1;//开始计算f,g,hnext.gcur.g5;//没有开根号为了提高精度next.hHeuristic(next);next.fnext.gnext.h;que.push(next);}}}
}int main(){int n,a1,a2;cinn;while(n--){cina1a2b1b2;memset(moves,0,sizeof(moves));//设置一块内存的值,//sizeof获取字节数Knight start;start.xa1;start.ya2;start.g0;start.hHeuristic(start);start.fstart.gstart.h;astart(start);while(!que.empty()) que.pop();coutmoves[b1][b2]endl;}return 0;
}
