1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 #include <map> 7 #define N 100010 8 using namespace std; 9 vector<int>Q[N]; 10 map<int,int>d; 11 bool vis[N]; 12 int n,a[N],b[N],x[N],y[N],cnt,ans; 13 void dfs(int x) 14 { 15 vis[x]=1; 16 for (int i=0;i<Q[x].size();i++) if (!vis[Q[x][i]]) dfs(Q[x][i]); 17 } 18 int main() 19 { 20 //freopen("duliu.in","r",stdin),freopen("duliu.out","w",stdout); 21 scanf("%d",&n); 22 for (int i=1;i<=n;i++) 23 { 24 scanf("%d",&a[i]),a[n+1]^=a[i]; 25 if (!d[a[i]]) d[a[i]]=++cnt; 26 } 27 if (!d[a[n+1]]) d[a[n+1]]=++cnt; 28 for (int i=1;i<=n;i++) 29 { 30 scanf("%d",&b[i]),b[n+1]^=b[i]; 31 if (!d[b[i]]) d[b[i]]=++cnt; 32 } 33 if (!d[b[n+1]]) d[b[n+1]]=++cnt; 34 memcpy(x,a,sizeof x),memcpy(y,b,sizeof y); 35 sort(x+1,x+n+2),sort(y+1,y+n+2); 36 for (int i=1;i<=n;i++) if (x[i]!=y[i]) { printf("-1"); return 0; } 37 for (int i=1;i<=n+1;i++) a[i]=d[a[i]],b[i]=d[b[i]]; 38 for (int i=1;i<=n;i++) if (a[i]!=b[i]) ans++,Q[a[i]].push_back(b[i]); 39 if (a[n+1]!=b[n+1]) Q[a[n+1]].push_back(b[n+1]); 40 for (int i=1;i<cnt;i++) if (Q[i].size()&&!vis[i]) dfs(i),ans++; 41 if (!vis[cnt]) ans++; 42 printf("%d",ans-1); 43 }
原文:https://www.cnblogs.com/Comfortable/p/9813438.html