a290 - 新手訓練系列 ~ 圖論
題目描述
題目要求判斷給定有向圖中，從起點城市 A 是否能到達終點城市 B。輸入包含城市數量 N、道路數量 M，以及 M 條有向邊。最後輸入起點 A 和終點 B，輸出 "Yes!!!" 如果 A 能到達 B，否則輸出 "No!!!"。
解題思路
本題可以使用深度優先搜尋 (DFS) 演算法來解決。首先，建立一個鄰接表來表示圖。然後，從起點 A 開始進行 DFS，遍歷所有可到達的城市。如果在 DFS 過程中到達了終點 B，則輸出 "Yes!!!"，否則輸出 "No!!!"。
複雜度分析
- 時間複雜度: O(N + M) (DFS 遍歷圖的頂點和邊)
- 空間複雜度: O(N) (鄰接表和訪問陣列)
程式碼
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> v;
vector<bool> vis;
void dfs(int from){
vis[from]=1;
for(auto i:v[from])
if(!vis[i]) dfs(i);
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n,m,a,b;
while(cin >> n >> m){
v.resize(n+1);
vis.assign(n+1, false);
while(m--){
cin >> a >> b;
v[a].push_back(b);
}
cin >> a >> b;
dfs(a);
(vis[b]==0)?cout << "No!!!\n":cout << "Yes!!!\n";
v.clear();
vis.clear();
}
}