個人使用了struct,裡面存了廠商的好壞與上游廠商(會有多個)
中文字請自行改掉盒盒 >:D
struct vendor{ bool 母湯 = 0; vector<vendor*> 上游廠商; };
再來用遞迴檢查廠商好壞: bool checkBad(vendor* 欲檢查的廠商){ // 用來檢查的函式 if(欲檢查廠商->母湯) return true; // 這個廠商本來就母湯,回傳true if(沒有上游廠商) return false; // 已經到最上游了(沒有上游廠商)都沒問題,代表這個廠商沒有問題,回傳false for(所有上游廠商跑一遍){ // 檢查所有上游廠商 if(checkBad(上游廠商)){ 欲檢查廠商->母湯 = 1; // 如果這個廠商的上游廠商有問題,遞迴走過的廠商都會被標成有問題,從而減少時間 return true; // 回傳true } } return false; // 如果所有上游廠商都沒有問題,代表這個廠商沒有問題,回傳false }
那個 欲檢查廠商->母湯 = 1 呢,有加能跑7ms,沒加得跑0.5s xDDD
接下來應該都沒問題了 (?) 就宣告vendor的陣列,把資料塞進去~
不知道能不能寫成尾遞迴用迴圈替代orz
後來查看前輩寫的,發現與 who_am_I 大大與 shawn2000100 大大寫的比較類似一點點 xD
至於為啥使用這個解法? 因為我看不懂只用C的解法 (太笨了 -.-