带权并查集

带权并查集的一些拙见

1635570411782

路径压缩

这是一个普通的并查集。如果我们对 $C$ 执行find操作，最终会得到 $A$ ，但是过程中会经过B。如果C的父亲特别多，这步就会消耗相当的时间，我们可以让 $C$ 直接指向 $A$ ，省去中间的操作进行优化，下图就是希望得到的结果

1635570596670

操作方法就是 将每个节点直接与其find操作最终得到的节点连接一条边 。在 $find$ 方法中实现

int findx(int x)
{
    if(x!=f[x])
    {
        f[x]=findx(f[x]);
    }
    return f[x];
}

带权并查集

1635570810836

这就是基于路径压缩的带权并查集的样子。可以看到，在普通并查集的基础上，带权并查集在边中添加了一些额外的信息可以更好的处理问题。在 边上记录额外的信息 的并查集就是 带权并查集

每一条边都记录了节点到根节点的一个权值。基于路径压缩就会产生两个问题：

我们希望得到的是 节点与根节点 的权值。但是在路径压缩之前，每个节点都是与 父节点 连接的，这个权值自然也是和其 父节点 的权值。因此在路径压缩的过程中，权值也应当做出更新。
在两个集团进行合并时，因为两个集团的根节点不同，需要把一个集团的根节点同时赋为另一个集团的根节点。自然也要进行权值的更新

带权并查集のfind

//value[x]表示节点x到根的权值
int findx(int x)
{
    if(x!=f[x])
    {
        int t=f[x];//记录父亲节点的编号
        f[x]=findx(f[x]);
        value[x]+=value[t];//父节点已经完成更新了
    }
    return f[x];
}

先记录下原本父节点的编号，接着路径压缩后父节点就会变成根节点，此时父节点的权值，已经是父节点到根节点的权值了。再加上当前节点与其父节点的权值，就会得到当前节点到根节点的权值

带权并查集のmerge

第一张图是 $merge$ 前，第二张图是 $merge$ 后

1635572555734

1635572674620

我们需要求出 $px$ 和 $py$ 这条边的权值为多少。显然 $x\rightarrow y\rightarrow py$ 和 $x\rightarrow px\rightarrow py$ 这两条边的权值之和应该相同。容易求出 $value[px]=value[y]+temp-value[x]$ （temp为题目给出的关系）。虽然思想一样，但实际上更新方法都是需要都是参考具体题目的，比如下面要讲的食物链

例题分析：

食物链

动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是"1 X Y"，表示X和Y是同类。
第二种说法是"2 X Y"，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1）当前的话与前面的某些真的话冲突，就是假话；
2）当前的话中X或Y比N大，就是假话；
3）当前的话表示X吃X，就是假话。
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。

在这个题目中，我们需要记录的关系就是食物链上的关系。因此带权并查集的权值为两个动物在食物链上的相对关系。定义 $A \rightarrow B$ $0$ 表示为同类， $1$ 表示为A吃B， $2$ 表示为B吃A

考虑如何更新value？

$A \rightarrow B=1,B \rightarrow C=1$ ，由题意得 $A \rightarrow C=2$

$A \rightarrow B=2,B \rightarrow C=2$ ，由题意得 $A \rightarrow C=1$

$A \rightarrow B=0,B \rightarrow C=1$ ，由题意得 $A \rightarrow C=1$

$A \rightarrow B=1,B \rightarrow C=2$ ，由题意得 $A \rightarrow C=0$

……

应该可以看出来 $A \rightarrow C=(A \rightarrow B + B \rightarrow C) mod 3$

考虑如何进行区间合并？

和我们最开始的板子相比，这道题就多了一个取模的操作，因此区间合并时加一句取模就行了

考虑如何判断矛盾？

已知 $A$ 与根节点的关系，已知 $B$ 与根节点的关系，这些都是自己通过并查集维护的。我们已经知道如何求出 $A \rightarrow B$ 的关系，当 $A$ 和 $B$ 是同一个根节点时只要我们求出的关系与题目给出的关系不同即可说明存在矛盾。如果 $A$ 和 $B$ 不是同一个根节点，我们就维护并查集。

1635575514008

$(val1-val2+3)mod3==temp$ ???

Warning!!!

题目只给出了1和2两种关系，0 1 2 是自己新定义的关系，需要处理一下。

#include<iostream>
using namespace std;
#define ll long long
#define MAXN 50005
ll n,m;
ll f[MAXN];ll val[MAXN];
ll temp;
ll ans;
int findx(int x)
{
    if(x!=f[x])
    {
        int t=f[x];
        f[x]=findx(f[x]);
        val[x]=(val[x]+val[t])%3;
    }
    return f[x];
}

void merge(int x,int y)
{
    int fx=findx(x);
    int fy=findx(y);
    if(fx==fy)
    {
        if(temp!=(val[y]-val[x]+3)%3)
            ans++;
    }
    else
    {
        f[fy]=fx;
        val[fy]=(val[x]+temp-val[y])%3;
    }
}

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++)
    {
        ll u,v;
        cin>>temp>>u>>v;
        if(u>n||v>n||(temp==2&&u==v))
        {
            ans++;
            continue;
        }
        if(temp==1) temp=0;//相同
        else if(temp==2) temp=1;//A吃B
        merge(u,v);
    }
    cout<<ans<<endl;
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

1635579105881

完完全全的模板题传送

题意：

求在有 $n$ 个数中，有 $m$ 次询问，每次询问在这给定的区间和这区间里数的和为 $sum$ ，求每次给出的是不是正确的 $sum$ 。也就是和前面的矛盾不矛盾。

考虑如何判断矛盾？

假设有两个线段 AB 和 AC (B>C) ，他们有共同的起点，已知 AB 和 AC 的长度。现在给出 CB 的长度，如果 $AB-AC \neq CB$ 即为出现了矛盾

考虑如何维护并查集？

定义一个点的根为他能到达的最左端的端点。维护的 $val$ 是这个节点和最左端节点的距离。

1635580976789

$temp=val1-val2$ ？

1635581844480

$???=val[x]+temp-val[y]$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 200005
int f[MAXN];
ll val[MAXN];
ll n, m;
ll ans = 0;
int findx(int x)
{
    if (f[x] != x)
    {
        int t = f[x];
        f[x] = findx(f[x]);
        val[x] += val[t];
    }
    return f[x];
}

void merge(int x, int y, ll temp) //x<y
{
    int fx = findx(x); //类似于前缀和，要减去1
    int fy = findx(y);
    if (fx == fy) //判断有没有矛盾
    {
        if (val[x] + temp != val[y])
        {
            ans++;
            return;
        }
    }
    else if (fx < fy)
    {
        f[fy] = fx;
        val[fy] = val[x] + temp - val[y];
    }
    else if (fy < fx)
    {
        f[fx] = fy;
        val[fx] = val[y] - temp - val[x];
    }
    int valfx, valfy;
    valfx = val[fx];
    valfy = val[fy];
}

void solve()
{
    while (cin >> n >> m)
    {
        for (int i = 0; i <= n; i++)
            f[i] = i;
        for (int i = 0; i <= n; i++)
            val[i] = 0;
        ans = 0;
        for (int i = 1; i <= m; i++)
        {
            int u, v;
            ll temp;
            cin >> u >> v >> temp;
            merge(u - 1, v, temp);
        }
        cout << ans << endl;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

然后是你最喜欢的CF

题意：

给出一些 $n$ 个单词，给出 $m$ 个关系：单词 $u$ 和单词 $v$ 是同义词 或 反义词 。如果这些关系和之前给出的关系出现了矛盾，输出NO，否则输出YES

再给出 $q$ 组询问，询问单词 $u$ 和 $v$ 的关系，有且仅有以下三种

同义词
反义词
毫无关系

思路：

同义词和反义词，emm，先写写看看

同义词的同义词是同义词

反义词的反义词是同义词

同义词的反义词是反义词

反义词的同义词是反义词

是不是有点像 01模数 ，分别对应

$(0+0) mod 2 = 0$

$(1+1)mod2=0$

$(1+0)mod2=1$

$(0+1)mod2=1$

考虑如何更新value？

上面已经给出了过程，同义词对应 $(val[x]+val[y]) mod2$ ，反义词对应 $(val[x]+val[y]+1)mod2$

考虑如何维护集团？

每有一条连边就加进来，集团内的成员元素只有两种关系，同义词或反义词

1635593939569

同义词 $(val[x]+val[y])mod2$
反义词 $(val[x]+val[y]+1)mod2$

考虑如何判断关系？

同一集团且不相等，反义词
同一集团且相等，同义词
非同一集团，非相关

考虑如何判断矛盾？

给出的关系是相反但是两个单词位于同一集团且值相等
给出的关系是相同但是两个单词位于同一集团且值不同

其他技巧：用map来映射字符串，这样可以正常的访问和使用并查集

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define MAXN 100005
ll n,m,q;
string s,v,u;
map <string,int> mp;//用int来映射字符串
int f[MAXN];
int val[MAXN];//对每个集团内的字符串通过0和1赋值来表示是不是近义词，反义词
//同义词的同义词是同义词 (0+0)%2
//反义词的反义词是同义词 (1+1)%2
int findx(int x)
{
    if(f[x]!=x)
    {
        int t=f[x];
        f[x]=findx(f[x]);
        val[x]=(val[x]+val[t])%2;
    }
    return f[x];
}

void solve()
{
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        mp[s]=i;//对字符串映射，这样就能通过正常的并查集访问了
        f[i]=i;
        val[i]=0;//开始默认所有词都是同义词（不是同一集团，没事）
    }
    int flag;
    while(m--)
    {
        cin>>flag>>u>>v;
        int x=mp[u];int y=mp[v];
        if(flag==1)//同义词
        {
            if(findx(x)==findx(y)&&val[x]!=val[y])//非法情况
            {
                cout<<"NO"<<endl;
                continue;
            }
            else//维护并查集
            {
                cout<<"YES"<<endl;
                int fx=findx(x);
                int fy=findx(y);
                f[fy]=fx;//这题难得顺序无所谓
                val[fy]=(val[x]+val[y])%2;               
            }
        }
        else//反义词
        {
            if(findx(x)==findx(y)&&val[x]==val[y])//非法情况
            {
                cout<<"NO"<<endl;
                continue;
            }
            else//维护并查集
            {
                cout<<"YES"<<endl;
                int fx=findx(x);
                int fy=findx(y);
                f[fy]=fx;
                val[fy]=(val[x]+val[y]+1)%2;          
            }
        }
    }
    while(q--)
    {
        cin>>u>>v;
        int x=mp[u];int y=mp[v];
        if(findx(x)==findx(y)&&val[x]!=val[y]) cout<<2<<endl;
        else if(findx(x)==findx(y)&&val[x]==val[y]) cout<<1<<endl;
        else if(findx(x)!=findx(y)) cout<<3<<endl;
    }
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    solve();

    return 0;
}