资源专业网站优化排名,工厂生产管理系统软件,美橙互联旗下网站,做网站的客户题解#xff1a;ABC277C - Ladder Takahashi
题目
链接#xff1a;Atcoder。
链接#xff1a;洛谷。
难度
算法难度#xff1a;普及。
思维难度#xff1a;入门。
调码难度#xff1a;入门。
综合评价#xff1a;简单。
算法
深度优先搜索简单图论
思路
把每…题解ABC277C - Ladder Takahashi
·题目
链接Atcoder。
链接洛谷。
·难度
算法难度普及。
思维难度入门。
调码难度入门。
综合评价简单。
·算法
深度优先搜索简单图论
·思路
把每个楼层看做是图的每个节点用dfs从1开始深度优先遍历整个图在经过每个节点的同时打擂台求出编号最大的节点的编号最终输出该编号。
·代价
O(n)。事实上在输入的边里没有提及的全是孤点所以真正能够遍历到的最多只有2n个点因此dfs在去重不重复经过一个相同的点后时间复杂度为o(n)。
·细节
对于边的存储和dfs去重时是否经过的判定我们分别采用map套vector以及map或离散化本人采用map处理。
·代码
#includebits/stdc.h
#define N 220000
using namespace std;
mapint,vectorintedge{};
mapint,boolbeto{};
int ans0,n0;
inline void dfs(int node);
int main(){scanf(%d,n);for(int i1;in;i){int a0,b0;scanf(%d%d,a,b);edge[a].push_back(b);edge[b].push_back(a);}dfs(1);printf(%d\n,ans);return 0;
}
inline void dfs(int node){ansmax(ans,node);if(beto[node]true){return;}beto[node]true;for(auto i:edge[node]){dfs(i);}
}
·注意
洛谷评测如果UKE就说明RemoteJudge炸掉了过一段时间几分钟到几年不等就好了。
