題解：ABC277C - Ladder Takahashi

·題目

鏈接：Atcoder。

鏈接：洛谷。

·難度

算法難度：普及。

思維難度：入門。

調碼難度：入門。

綜合評價：簡單。

·算法

深度優先搜索+簡單圖論

·思路

把每個樓層看做是圖的每個節點，用dfs從1開始深度優先遍歷整個圖，在經過每個節點的同時打擂臺求出編號最大的節點的編號，最終輸出該編號。

·代價

O(n)。事實上在輸入的邊里沒有提及的全是孤點，所以真正能夠遍歷到的最多只有2n個點，因此dfs在去重（不重復經過一個相同的點）后時間復雜度為o(n)。

·細節

對于邊的存儲和dfs去重時是否經過的判定，我們分別采用map套vector，以及map或離散化（本人采用map）處理。

·代碼

#include<bits/stdc++.h>
#define N 220000
using namespace std;
map<int,vector<int>>edge={};
map<int,bool>beto={};
int ans=0,n=0;
inline void dfs(int node);
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){int a=0,b=0;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){ans=max(ans,node);if(beto[node]==true){return;}beto[node]=true;for(auto i:edge[node]){dfs(i);}
}

·注意

洛谷評測如果UKE，就說明RemoteJudge炸掉了，過一段時間（幾分鐘到幾年不等）就好了。