G. Columns Swaps(并查集)

G. Columns Swaps

题目大意：

两行$n$列，一次操作可以交换同列两个数，要求最小操作次数使两行都是$1-n$的排列。

前置知识：

$k-sat$问题。
简单讲就是给你多个命题，问是否存在可行解使所有命题成立，$k$就是单个命题的条件数（好像不叫这个 ）。
解决方法一般是建图，缩点，当单个条件正否出现在同一强连通分量时无解。
本题的本质是$2-sat$问题。（$p|q$命题类型）

思路：

每个数都要出现两次这是必要条件。
如果一个数两次出现在同一行，必须一假一真
如果一个数两次出现在不同行，必须同真同假
可以发现本题是无向边（和第几次出现无关），可以用并查集实现。
编号$i$ 表示真$i+n$表示假。
并查集的合并：

			for(int i=1;i<=n;i++){  // li 表示第i次出现的列，hi同理
				if(h1[i]==h2[i]){  // 同一行
					work(l1[i],l2[i]+n);
					work(l2[i],l1[i]+n);
				}
				else if(l1[i]!=l2[i]){  // 不同行不同列
					work(l1[i],l2[i]);
					work(l1[i]+n,l2[i]+n);
				}
			}
1
2
3
4
5
6
7
8
9
10

所有条件的真假不在同一连通块内就一定有解。
操作次数最小：
并查集在合并时，维护每个连通块内真的个数。（也就是操作数）
当前的连通块如果没有作决策选择真假两个块里最小的即可。

				queue<int> ans;
				for(int i=1;i<=n;i++){
					int s1=find(i),s2=find(i+n); // 找块
					if(vis[s1]==0){  // 还没确定
						if(_size[s1]<_size[s2]){  // 选真更好
							vis[s1]=1;
							vis[s2]=-1;
						}
						else{
							vis[s2]=1;
							vis[s1]=-1;
						}
					}
					if(vis[s1]==1) ans.push(i); 
				}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

注意初始化，二倍空间。

Code:

#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#include <string>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
//#include <unordered_map>
#define guo312 std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ll long long
#define Inf LONG_LONG_MAX
#define inf INT_MAX
#define endl "\n"
#define PI 3.1415926535898
using namespace std;
const int N=4e5+10;
int n;
int a[2][N];
map<int,int> mp;
int h1[N],h2[N],l1[N],l2[N];

int flag[N],_size[N],vis[N];
void init(){
	for(int i=1;i<=n*2;i++){
		flag[i]=i,_size[i]=1,vis[i]=0;
		if(i>n) _size[i]=0;
	}
}

int find(int x){
	if(flag[x]==x){
		return x;
	}
	else{
		return flag[x]=find(flag[x]);
	}
}

void work(int x,int y){
	int s1=find(x),s2=find(y);
	if(s1==s2) return ; 
	_size[s1]+=_size[s2],flag[s2]=s1;
}

bool ok1(){
	for(auto it:mp){
		if(it.second!=2) return 0;
	}
	return 1;
}

bool ok2(){
	for(int i=1;i<=n;i++){
		int s1=find(i),s2=find(i+n);
		if(s1==s2) return 0;
	}
	return 1;
}

int main(){
guo312;
	int t; cin>>t; 
	while(t--){
		cin>>n; mp.clear(); init();
		for(int j=0;j<=1;j++){
			for(int i=1;i<=n;i++){
				cin>>a[j][i];
				mp[a[j][i]]++;
				if(mp[a[j][i]]==1){
					h1[a[j][i]]=j;
					l1[a[j][i]]=i;
				}
				else{
					h2[a[j][i]]=j;
					l2[a[j][i]]=i;
				}
			}
		}
		if(ok1()){
			for(int i=1;i<=n;i++){
				if(h1[i]==h2[i]){
					work(l1[i],l2[i]+n);
					work(l2[i],l1[i]+n);
				}
				else if(l1[i]!=l2[i]){
					work(l1[i],l2[i]);
					work(l1[i]+n,l2[i]+n);
				}
			}
			if(ok2()){
				queue<int> ans;
				for(int i=1;i<=n;i++){
					int s1=find(i),s2=find(i+n);
					if(vis[s1]==0){
						//cout<<_size[s1]<<" "<<_size[s2]<<" "<<s1<<" "<<s2<<endl; 
						if(_size[s1]<_size[s2]){
							vis[s1]=1;
							vis[s2]=-1;
						}
						else{
							vis[s2]=1;
							vis[s1]=-1;
						}
					}
					if(vis[s1]==1) ans.push(i); 
				}
				cout<<ans.size()<<endl;
				while(!ans.empty()){
					int s=ans.front(); ans.pop();
					cout<<s<<" "; 
				}
				cout<<endl;
			}
			else{
				cout<<"-1"<<endl;
			}
		}
		else{
			cout<<"-1"<<endl;
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131