【TOI2019 二模 pD】離不開的新手村
題目敘述 給定一張$\color{white}{\space N\space}$點$\color{white}{\space M\space}$邊的有向圖，每個點有他的難度滿足「難度介於$\color{white}{\space 1\sim N\space}$之間」且「任兩個點難度相異」。 一個數字$\color{white}{\space i\space}$滿足「從任意的難度$\color{white}{\space \leq i\space}$的節點出發時，怎麼走都不會走到難度$\color{white}{\space >i\space}$的節點」時，數字$\color{white}{\space i\space}$就是『好的』，請你計算這張圖『好的』數字種類(介於$\color{white}{\space 1\sim N\space}$之間)。 接下來會有$\color{white}{\space Q\space}$次修改，每次修改會交換某兩個節點上的難度，請在每次修改後輸出新的『好的』數字種類。 子任務1(5分)：$\color{white}{\space 1\leq N,M \leq 100,1\leq Q \leq 100\space}$。 子任務2(16分)：圖是一條有向路徑。 子任務3(13分)：$\color{white}{\space M=N-1\space}$，每個點皆存在走到節點$\color{white}{\space 1\space}$的有向路徑。 子任務4(10分)：$\color{white}{\space 1\leq Q \leq 1000,|a-b|\leq 10000\space}$。 子任務5(25分)：每個點的入度不超過$\color{white}{\space 10\space}$。 子任務6(31分)：$\color{white}{\space 1\leq N,M \leq 500000,1\leq Q \leq 50000\space}$。 Time limit: 15 second 範測測資 Input: 5 5 1 2 3 4 5 2 4 3 1 2 1 4 3 5 3 3 2 4 2 3 5 3