e792 - a3.旅行(Trip)
題目描述
題目描述了小軒想要從一個國家出發，透過飛機航班到達另一個國家。給定國家數量、航班資訊以及查詢，程式需要判斷對於每次查詢，起點國家是否可以到達終點國家。
解題思路
這題可以使用深度優先搜尋 (DFS) 來解決。我們可以將國家視為圖的節點，航班視為圖的邊。對於每次查詢，從起點國家開始進行 DFS，如果能夠到達終點國家，則輸出 "YES"，否則輸出 "NO"。為了避免無限迴圈，我們需要使用一個 visited 陣列來記錄已經訪問過的國家。
複雜度分析
- 時間複雜度: O(Q * (N + M))，其中 Q 是查詢次數，N 是國家數量，M 是航班數量。在最壞情況下，對於每個查詢，DFS 可能需要遍歷所有國家和航班。
- 空間複雜度: O(N)，主要用於儲存 visited 陣列和 DFS 的遞迴堆疊。
程式碼
#include <iostream>
using namespace std;
int n,m,q,x,y;
bool a[201][201],ans;
void fd(int now,int t,bool c[201]){
if(now==y){
ans=1;
return;
}
if(t==n||ans||c[now])return;
c[now]=1;
for(int i=0;i<n;++i){
if(a[now][i]){
fd(i,t+1,c);
}
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> m >> q;
while(m--){
cin >> x >> y;
a[x][y]=1;
}
while(q--){
cin >> x >> y;
bool chat[201]={0};
ans=0;
fd(x,0,chat);
if(ans)
cout << "YES\n";
else
cout << "NO\n";
}
}