hdu5495 LCS （群論/并查集）

題意：

選擇一種排列，使得數組a和b有更多的相同子序列。

例如，例1：1 2 3 和 3 2 1 ；p可以為2 1 3；

是以排列為 a2 a1 a3 和 b2 b1 b3.

即 2 1 3 和 2 3 1； 此時 2 1 是相同子序列， 長度為2；

再例如 ， 例2：

6

1 5 3 2 6 4

3 6 2 4 5 1

可以看成

1 3 2 4 5 6

3 2 4 1 6 5

第一個部分，可以排序得到

1 4 2 3

3 1 4 2

子序列長度為 4 - 1；（如果an != bn 是以每個部分的長度 最長為 每個子序列的長度 - 1， 如果an == bn , 每個部分的長度 最長為 每個子序列的長度, 則 每個an 可以看出一個部分）

if 部分的長度 == 1， 則 ans ++；

else ans += (部分的長度 - 1);

此時 ans = （4 - 1） + （2 - 1） = 4；

群置換代碼如下

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAX = 1e5 + 5;
int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        int N;
        scanf("%d", &N);
        int a[MAX],b[MAX],c[MAX];//c[]的作用是 幫助 找到每個部分的集合
        bool vis[MAX] = {0};
        for(int i = 1; i <= N; i++) {
            scanf("%d", &a[i]);
            c[a[i]] = i;
        }
        for(int i = 1; i <= N;  i++) scanf("%d", &b[i]);
        int ans = 0;
        for(int i = 1; i <= N; i++) {
            int t = 1;
            if(!vis[a[i]]) {
                int pos = a[i];
                int x = b[i];
                while(pos != x) {
                    vis[a[c[x]]] = 1;
                    x = b[c[x]];
                    t++;
                }
                if(t == 1) ans++;
                else ans += (t - 1);
            }
        }
        printf("%d\n", ans);
    }
}
           

其實兩種做法隻是找集合的方法不一樣。

并查集的代碼如下

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAX = 1e5 + 5;
int a[MAX] , b[MAX];
int fa[MAX] , t[MAX];
void init(int n) {
 for(int i = 0 ; i <= n ; i++) {
        fa[i] = i;
        t[i] = 1;
    }
}

int find(int x) {
 if(x != fa[x])
 fa[x] = find(fa[x]);
 return fa[x];
}

void Union(int x , int y) {
 int xx = find(x);
 int yy = find(y);
 if(xx != yy) {
        fa[x] = yy;
        t[yy] += t[xx];
	}
}

int main() {
int T;
scanf("%d" , &T);
  while(T--) {
      int N;
        scanf("%d" , &N);
      init(MAX);
        for(int i = 0 ; i < N; i++) {
       scanf("%d" , &a[i]);
        }
        for(int i = 0 ; i < N ; i++) {
                scanf("%d" , &b[i]);
                Union(a[i] , b[i]);
        }
        int ans = 0;
        for(int i = 0 ; i < N ; i++) {
         if(fa[a[i]] == a[i]) {
                 if(t[a[i]] == 1) {
                  ans++;
                 }
                 else {
                  ans += (t[a[i]] - 1);
                 }
                 }
          }
          printf("%d\n" , ans);
    }
    return 0;
}