c139 - 00291 - The House Of Santa Claus
題目描述
題目要求找出從節點 1 開始，經過所有邊恰好一次，並回到節點 1 的所有路徑，也就是尋找圖中的 Euler path。題目給定的圖是一個固定的五邊形結構，節點編號為 1 到 5。
解題思路
這題可以使用深度優先搜尋 (DFS) 搭配回溯法來解決。我們從節點 1 開始，每次選擇一個尚未走過的邊，將其標記為已走過，然後遞迴地探索下一個節點。當我們走過所有邊（即路徑長度為 9）時，輸出路徑。回溯時，將邊標記為未走過，以便探索其他可能的路徑。由於題目要求輸出所有可能的路徑，因此需要窮舉所有可能性。
複雜度分析
- 時間複雜度: O(V^E)，其中 V 是節點數量 (5)，E 是邊的數量 (8)。在最壞情況下，需要探索所有可能的路徑。
- 空間複雜度: O(V)，主要用於儲存遞迴堆疊和
stk陣列。
程式碼
#include <bits/stdc++.h>
using namespace std;
int stk[10];
vector <pair <int,int>> e={{5,4},{5,3},{5,2},{5,1},{4,3},{3,2},{3,1},{2,1}};
bool E[6][6],has[6][6];
void dfs(int it,int sz){
if(sz==9){
for(int i=0;i<sz;++i){
cout << stk[i];
}
cout << "\n";
return;
}
for(int i=1;i<=5;++i){
if(E[it][i]&&!(has[it][i])&&!(has[i][it])){
stk[sz]=i;
has[it][i]=1;
dfs(i,sz+1);
has[it][i]=0;
}
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
for(int i=0;i<e.size();++i)
E[e[i].second][e[i].first]=E[e[i].first][e[i].second]=1;
stk[0]=1;
dfs(1,1);
}