并查集
将同一循环的数合并
#include <iostream>
using namespace std;
const int N = 110;
int n, a[N], b[N];
int p[N], si[N];
int find(int x){
p[x] = (p[x] == x)?x:find(p[x]);
return p[x];
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
for(int i = 1; i <= n; i++) p[i] = i, si[i] = 1;
int res = n, m = 1;
for(int i = 1; i <= n; i++){
if(a[i] == b[i]) res--;
else{
if(find(a[i]) != find(b[i])){
res--;
si[find(b[i])] += si[find(a[i])];
p[find(a[i])] = find(b[i]);
m = max(m, si[find(b[i])]);
}
}
}
if(res == 0) cout << res << " -1" << endl;
else
cout << res << " " << m << endl;
return 0;
}
好妙!
有一个问题,大佬请问一组内要移动一个其它牛必须一起同时移动吗,还是说可以先只移动几个,保持其他几个不动。难道是说这里不需要考虑组内是否能循环移动成功嘛。
比如像下面这组样例,看着好像是无解的啊,但是出来的结果却是 1 4
是同时移动的, 但是不需要保持原来的相对位置。 这个case 你可以看成 牛一 到了位置4 (挤掉了牛四) , 牛四去了位置2 (挤掉了牛二),牛二去了位置3(挤掉了牛三),牛三去了位置1 (这个位置是空的)
原来是这样,看来我也没读懂,我做的时候默认它一定合法了,没仔细想
tql
谢谢大佬,现在懂了
想法好好