D. Mahmoud and a Dictionary 种类并查集

http://codeforces.com/contest/766/problem/D

所谓种类并查集，题型一般如下：给定一些基本信息给你，然后又给出一些信息，要求你判断是真是假。例如给出a和b支持不同的队伍，而且b和c也是支持不同的队伍，由于队伍只有两支（就是说只有两种），所以可以推出a和c是支持同一个队伍。

你可能会想用两个并查集，一个并查集存放一个队伍。但是这样是不行的，十分麻烦。因为你想想，如果给出[a,b]不同，然后[c,d]不同，如果我按照左边的放在同一个集合，那么我接着[a,c]不同，这样就会是(a,d)相同，这样的话，你要更改那个并查集，是十分麻烦的。

正解：只用一个并查集，而且再维护一个数组rank[i]表示i与father的关系，0表示支持同一个球队，1表示不同，这样的话，就可以根据rank[x]==rank[y]来判断是不是支持相同的了。爸爸支持谁没所谓啊，我们不关心支持哪个球队，我们只关心支持的是否一样罢了。rank[]数组压缩路径和并查集一样的，只不过其中要列些数据，推些公式出来。

大致思路和食物链那些题目差不多。

设rex[i]表示i号顶点和爸爸的关系是什么

0，表示同一类型，1表示不同类型。

然后细心推个公式，就行了

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

const int maxn = 1e5 + ;

int fa[maxn], rex[maxn];

map<string, int>mp;

int tofind(int u) {

    if (fa[u] == u) {

        rex[u] = ;

        return u;

    }

    int t = fa[u];

    fa[u] = tofind(fa[u]);

    rex[u] = (rex[u] + rex[t]) % ;

    return fa[u];

}

int tomerge(int x, int y, int val, int is) {

    int tx = x, ty = y;

    x = tofind(x);

    y = tofind(y);

    if (is) {

        if (x != y) return ;

        if (rex[tx] != rex[ty]) {

            return ;

        } else return ;

    }

    if (x != y) {

        fa[y] = x;

        rex[x] = ;

        rex[y] = (rex[ty] + rex[tx] + val) % ;

        return ;

    }

    return !((rex[tx] + rex[ty] + val) % );

}

void work() {

    int n, m, q;

    cin >> n >> m >> q;

    for (int i = ; i <= n; ++i) {

        string s;

        cin >> s;

        mp[s] = i;

        fa[i] = i;

    }

    for (int i = ; i <= m; ++i) {

        int id;

        string s1, s2;

        cin >> id >> s1 >> s2;

        id--;

        if (tomerge(mp[s1], mp[s2], id, )) {

            cout << "YES" << endl;

        } else cout << "NO" << endl;

    }

    for (int i = ; i <= q; ++i) {

        string s1, s2;

        cin >> s1 >> s2;

        cout << tomerge(mp[s1], mp[s2], , ) << endl;

    }

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    IOS;

    work();

    return ;

}

巴特西

D. Mahmoud and a Dictionary 种类并查集

最新文章

热门文章