d536 - 3. 圖形迴圈偵錯問題
題目描述
題目要求判斷一個有向圖中是否存在迴圈，如果存在，則輸出最短迴圈的連結數。如果不存在迴圈，則輸出 0。圖形由連結表示，連結由兩個大寫字母組成，表示從第一個字母對應的節點到第二個字母對應的節點存在單向邊。
解題思路
使用深度優先搜尋 (DFS) 來遍歷圖形。在 DFS 的過程中，使用 used 陣列記錄當前節點是否已被訪問。如果 DFS 過程中再次遇到已被訪問的節點，則說明存在迴圈。在找到迴圈時，記錄迴圈的長度，並更新最短迴圈的長度。遍歷所有節點作為起點，以確保找到的是最短迴圈。
複雜度分析
- 時間複雜度: O(V + E)，其中 V 是節點數，E 是邊數。因為 DFS 最多會遍歷所有節點和邊。
- 空間複雜度: O(V)，主要用於
used陣列和 DFS 的遞迴堆疊。
程式碼
#include <iostream>
using namespace std;
int n,e[55][55],ans=55,used[55];
string s;
void dfs(int p,int step){
if(step>=ans)return;
//cout << p << " " << step << "\n";
if(used[p]){
ans=step;
return;
}
used[p]=1;
for(int i=0;i<55;++i){
if(e[p][i]){
dfs(i,step+1);
}
}
used[p]=0;
}
int main(){
cin >> n;
for(int i=0;i<n;++i){
cin >> s;
e[s[0]-'A'][s[1]-'A']=1;
}
for(int i=0;i<55;++i){
dfs(i,0);
}
if(ans!=55){
cout << ans;
}
else{
cout << "0";
}
}