Codeforces #28 B pSort

題意﹕給出一數組A[1..N]，並且A[i] = i，規定A[i]能和A[j]交換數值若且僅若|i-j| = d_i。問能否通過不限次數的交換使得最初的數組A變成目標的排列。

想了一會，其實方法也是挺簡單的﹕定義交換集G = {g_i} 使得A[g_i]能和A[g_j]交換數值。
關鍵是﹕交換集裡的元素可以組成任意排列。例如G = {1, 3, 5, 6}而數組是
1 ? 3 ? 5 6 ? ? ?
我們可以任意排列1, 3, 5, 6的位置，即可以排列成(舉例)
3 ? 5 ? 1 6 ? ? ?

因此，答案是顯然易見的﹕對於目標排列B, 該排列能夠達成若且僅若B[i]和i是屬於同一交換集G之中。

建立交換集的方法有很多，我的方法是用並查集。