此文由來 小時候看劉汝佳的訓練指南裡面 2-SAT 求解,做完 SCC 還要 for loop dfs,看起來很麻煩,後來看 E-Maxx Algorithms 裡的 2-SAT 教學才發現有很簡單的求解法,可是我比較笨,他的證明一直看不太懂,今天在校草級高顏值大肌肌學霸林庭風推薦的優質程式討論區「Taiwan 程式語言讀書會」裡看到有人在問上面那種構造法的正確性,我認真想了一小時多終於會證了。(討論區文章連結) 以下節錄自我的回文(之後可能會把它修好一點): 假設 2-SAT 做完強連通分解並把 SCC 依拓樸順序由小到大編號 那麼下面的演算法為什麼能構出一組解 for v = 1 to n: if SCC_ID[v] == SCC_ID[~v]: return NO ANSWER
4/15/2022資奧 2021 一中資奧研習投影片 https://hackmd.io/@pr3pony/ryatT5Skd 便宜的演算法比賽網路資源整理 https://hackmd.io/@pr3pony/HysEHoYe8 Vim 教學 http://www.csie.ntu.edu.tw/~b06902052/vim-slide/ debug 技巧(?)
2/8/20222021 一中資奧研習 slide: https://bit.ly/2M2ueUN Who am I? 張集貴 pr3pony :heart: :carousel_horse: i use arch btw
6/29/2021