題意：

給一些單詞，它們可能是同義或者反義，給出一些關(guān)系定義，從前面的定義開始建立關(guān)系，如果有的關(guān)系定義和之前的沖突輸出NO,否則輸出YES。然后查詢q次單詞x和單詞y的關(guān)系。

解題思路：

很明顯就是帶權(quán)并查集，但是我不太會(huì)用，去網(wǎng)上找了食物鏈的代碼，改了下代碼，但是每改公式，強(qiáng)行把關(guān)系差為2和3的都當(dāng)做反義關(guān)系，結(jié)果錯(cuò)了。結(jié)束后去學(xué)習(xí)了下帶權(quán)并查集，然后直接把公式改了改就過了，發(fā)現(xiàn)其實(shí)當(dāng)時(shí)xjb改也能過。

用一個(gè)數(shù)組rank[x]表示x和他的祖先直接的關(guān)系，0表示他們是同義，1表示他們是反義。

點(diǎn)于點(diǎn)之間的關(guān)系可以用向量來理解，為什么是向量我也不知道。比如說題目定義x與y的關(guān)系為x->y,那么x->fa[y]=x->y+y->fa[y]。也就是rank[x]=x與y的關(guān)系+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)//找尋父節(jié)點(diǎn)+路徑壓縮{    if(x==fat[x])        return fat[x];    int y=Find(fat[x]);    ran[x]=(ran[x]+ran[fat[x]])%2;//遞歸后從祖先節(jié)點(diǎn)向后到每個(gè)孩子來計(jì)算    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)//共父節(jié)點(diǎn)才能判斷出關(guān)系        {            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;//連接兩父節(jié)點(diǎn)        ran[x1]=(-ran[xx]+e-1+ran[yy]+2)%2;        /*這里只對(duì)祖先x1賦值，可能有童鞋就疑問為什么xx沒有賦值，其實(shí)xx在路徑壓縮里會(huì)根據(jù)          它和祖先的關(guān)系賦值,所以這里不用對(duì)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)//共父節(jié)點(diǎn)才能判斷出關(guān)系        {            int ans=(ran[xx]-ran[yy]+2)%2+1;            printf("%d/n", ans);        }        else printf("3/n");    }    return 0;}