cf 766 d Mahmoud and a Dictionary（带权并查集）

题意：

给一些单词，它们可能是同义或者反义，给出一些关系定义，从前面的定义开始建立关系，如果有的关系定义和之前的冲突输出NO,否则输出YES。然后查询q次单词x和单词y的关系。

解题思路：

很明显就是带权并查集，但是我不太会用，去网上找了食物链的代码，改了下代码，但是每改公式，强行把关系差为2和3的都当做反义关系，结果错了。结束后去学习了下带权并查集，然后直接把公式改了改就过了，发现其实当时xjb改也能过。

用一个数组rank[x]表示x和他的祖先直接的关系，0表示他们是同义，1表示他们是反义。

点于点之间的关系可以用向量来理解，为什么是向量我也不知道。比如说题目定义x与y的关系为x->y,那么x->fa[y]=x->y+y->fa[y]。也就是rank[x]=x与y的关系+rank[y];

#include <bits/stdc++.h>using namespace std;const int maxn=1e5+5;struct p{    char x[22];}a[maxn+5];int fat[maxn],ran[maxn], n;bool cmp(p a, p b){    if(strcmp(a.x,b.x)<0)return true;    else return false;}int fin(char key[]){    int l=1, r=n, mid=(1+n)/2;    while(l<=r)    {        mid=(l+r)/2;        if(strcmp(key, a[mid].x)>0)        {            l=mid+1;        }        else if(strcmp(key, a[mid].x)<0)        {            r=mid-1;        }        else return mid;//        PRintf("%d %s/n", mid, a[mid].x);    }    return 0;}void Init(int n)//初始化重要{    for(int i=1; i<=n; i++)    {        fat[i]=i;//初始化都是指向（看做）自己        ran[i]=0;//0同义 1反义    }    return;}int Find(int x)//找寻父节点+路径压缩{    if(x==fat[x])        return fat[x];    int y=Find(fat[x]);    ran[x]=(ran[x]+ran[fat[x]])%2;//递归后从祖先节点向后到每个孩子来计算    return fat[x]=y;//路径压缩}int main(){    int  m, q;    scanf("%d%d%d", &n, &m, &q);    int i;    for(i=1; i<=n; i++)scanf("%s", a[i].x);    sort(a+1, a+n+1, cmp);    Init(n);    int e, xx, yy;    char x[22], y[22];    for(i=0; i<m; i++)    {        scanf("%d%s%s", &e, x, y);        xx=fin(x);        yy=fin(y);        int x1=Find(xx);        int y1=Find(yy);//        printf("%d %d/n", x1, y1);        int ans=0;        if(x1==y1)//共父节点才能判断出关系        {            if((ran[xx]-ran[yy]+2)%2==e-1)                printf("YES/n");            else printf("NO/n");        }        else printf("YES/n"), ans=1;        if(ans)        {        fat[x1]=y1;//连接两父节点        ran[x1]=(-ran[xx]+e-1+ran[yy]+2)%2;        /*这里只对祖先x1赋值，可能有童鞋就疑问为什么xx没有赋值，其实xx在路径压缩里会根据          它和祖先的关系赋值,所以这里不用对xx赋值*/        }    }    for(i=0; i<q; i++)    {        scanf("%s%s", x, y);        xx=fin(x);        yy=fin(y);        int x1=Find(xx);        int y1=Find(yy);        if(x1==y1)//共父节点才能判断出关系        {            int ans=(ran[xx]-ran[yy]+2)%2+1;            printf("%d/n", ans);        }        else printf("3/n");    }    return 0;}