E. Cross Swapping（并查集变形/好题）

题目 参考

题意

给定一个n*n的二维矩阵。 执行操作：选择 1 < = k < = n ， s w a p ( a [ i ] [ k ] , a [ k ] [ i ] ) , 1 < = i < = n 1<=k<=n，swap(a[i][k], a[k][i]),1<=i<=n 1<=k<=n，swap(a[i][k],a[k][i]),1<=i<=n 比如当n=4，k=3时，转化后如右图所示。

对于上述操作，我们可以执行任意次，也可以是0次。 问，通过执行以上若干次，可以得到的字典序最小的二维数组是啥。

定义二维数组a的字典序为： 将二维数组a映射到一维数组b，映射规则 b[i*n+j] = a[i][j] 二维数组a1字典序小于二维数组a2， 当前仅当它们的映射b1 , b2满足 存在 i , b 1 [ j ] = = b 2 [ j ] , 1 < = j < i ; b 1 [ i ] < b 2 [ i ] i, b1[j] == b2[j], 1<=j