敌对并查集

本人在OIWIKI上看并查集相关资料时没发现敌对并查集相关内容，于是写一篇专栏来记录。

题目链接：P1525关押罪犯

思路

开两个并查集，分别对应朋友和敌人，以冲突事件影响力从大到小排序，依次放入并查集中。

具体来说，设并查集为A与B，一元素为p，p与p+n为矛盾事件（即假设p的敌人为p+n）。

放入方式是：设并查集为A与B，两矛盾为p与q。将p与q+n连接，将q与p+n连接（q与p是敌人，而p+n是p的敌人，p与q之间的矛盾是最大的，故p与q不能放同一监狱，故p与q+n，即q的敌人放同一监狱）。

当进行到要放的两矛盾已在同一监狱时，结束输出两元素的矛盾值。

代码

#include <cstdio>
#include <cctype>
#include <algorithm>
int read() //快速读入，可忽略
{
    int ans = 0;
    char c = getchar();
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
    {
        ans = (ans << 3) + (ans << 1) + c - '0';
        c = getchar();
    }
    return ans;
}
struct data  //以结构体方式保存便于排序
{
    int a, b, w;
} C[100005];
int cmp(data &a, data &b)
{
    return a.w > b.w;
}
int fa[40005], rank[40005];  //以下为并查集
int find(int a)
{
    return (fa[a] == a) ? a : (fa[a] = find(fa[a]));
}
int query(int a, int b)
{
    return find(a) == find(b);
}
void merge(int a, int b)
{
    int x = find(a), y = find(b);
    if (rank[x] >= rank[y])
        fa[y] = x;
    else
        fa[x] = y;
    if (rank[x] == rank[y] && x != y)
        rank[x]++;
}
void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        rank[i] = 1;
        fa[i] = i;
    }
}
int main()
{
    int n = read(), m = read();
    init(n * 2); //对于罪犯i，i+n为他的敌人
    for (int i = 0; i < m; ++i)
    {
        C[i].a = read();
        C[i].b = read();
        C[i].w = read();
    }
    std::sort(C, C + m, cmp);
    for (int i = 0; i < m; ++i)
    {
        if (query(C[i].a, C[i].b))  //试图把两个已经被标记为“朋友”的人标记为“敌人”
        {
            printf("%d\n", C[i].w); //此时的怒气值就是最大怒气值的最小值
            break;
        }
        merge(C[i].a, C[i].b + n);
        merge(C[i].b, C[i].a + n);
        if (i == m - 1)  //如果循环结束仍无冲突，输出0
            puts("0");
    }
    return 0;
}

题目链接：P2024食物链

思路

题目中的元素关系为三个，分别是同级，捕食，被捕食，故可开三个并查集来对应这种关系。

开三个并查集分别是同级，捕食与被捕食。（有一点要注意，题目指出若a捕食b，b捕食c，则c捕食a）

设两元素为p，q，若遇到同级时，在三个并查集内部连接p与q，若为捕食，则连接p与q+n，p+n与q+2n，p+2n与q（p为被捕食，p+n为同级，p+2n为捕食）。

当出现矛盾时输出即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n;
int k;
const int maxn=50005;
int fa[3*maxn];
int find(int x){
    if(fa[x]==x)return fa[x];
    else return find(fa[x]);
}
int main() {
    cin>>n>>k;
    int a,u,v;
    int ans=0;
    for(int i=1;i<=3*maxn-3;i++){
        fa[i]=i;
    }
    while(k--){
        cin>>a>>u>>v;
        if(a==1){
            if(u>n||v>n){
                ans++;
                continue;
            }
            else if(find(u+n)==find(v)||find(v+n)==find(u)){
                ans++;
                continue;
            }
            else{
                fa[find(u)]=find(v);
                fa[find(u+n)]=find(v+n);
                fa[find(u+2*n)]=find(v+2*n);
                }
        }
        if(a==2){
            if(u>n||v>n){
                ans++;
                continue;
            }
            else if(u==v){
                ans++;
                continue;
            }
            else if(fa[find(u)]==fa[find(v)]||fa[find(u)]==fa[find(v+n)]){
                ans++;
                continue;
            }
            else{
                fa[find(u+n)]=find(v);
                fa[find(u+2*n)]=find(v+n);
                fa[find(u)]=find(v+2*n);
            }
        }
    }
    cout<<ans;
    return 0;
}