Gym – 101173F Free Figurines 思维题+并查集

Problem F: Free Figurines 并查集

Source

Central Europe Regional Contest 2016      Zagreb, November 1820, 2016

Gym - 101173F

My Solution

题意：给出一个序列ai 表示i的父节点是ai, 再给出一个序列bi 表示i的父节点是 bi，求i < ai, ai为0则表示没有父节点，否则ai都不相等，bi同理。

只能进行2个操作，1、 把一个没有父节点的节点 作为 一个 没有父节点和子节点的 节点 的子节点， 代价为 1；

2、把一个没有父节点的节点的子节点去掉，代价为1；

思维题+并查集

关键是正确的读懂2个操作，即可，即只能对free的节点进行操作，所以当ai!=bi时，要先把ai拆掉，但必须先满足ai为free才能把i变成free，

同理把i插到bi上时也要满足bi节点为free(即该节点没有父节点)。

时间复杂度 O(n)

空间复杂度 O(n)

#include 
#include 

using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 8;

int a[MAXN], b[MAXN], fa;

int main()
{
    #ifdef LOCAL
    freopen("f.txt", "r", stdin);
    //freopen("f.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int n, i, ans = 0, t;
    cin >> n;
    for(i = 1; i <= n; i++){ cin >> a[i];
    }
    for(i = 1; i <= n; i++){ cin >> b[i];
    }
    for(i = 1; i <= n; i++){
        if(a[i] == b[i]) continue;
        if(a[i] != 0){
            ans++;
            fa = a[i];
            a[i] = 0;
            while(a[fa]){
                t = fa;
                fa = a[fa];
                a[t] = 0;
                ans++;
            }
        }
    }
    for(i = 1; i <= n; i++){
        if(a[i] == b[i]) continue;
        if(b[i] != 0){
            fa = a[b[i]];
            if(fa){
                a[b[i]] = 0;
                ans++;
            }
            else{
                continue;
            }
            while(a[fa]){
                t = fa;
                fa = a[fa];
                a[t] = 0;
                ans++;
            }
        }
    }
    for(i = 1; i <= n; i++){
        if(a[i] == b[i]) continue;
        ans++;
    }
    cout << ans << endl;



    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx