GYM 101243 F.Vitamins【思维+并查集】

题目大意：

现在有N个物品，已知有M个信息，表示两个物品谁更重，或者一样重，现在有三种重量，WRB，从大到小递减，问我们能够确定哪些物品的重量，如果不确定的，输出？否则输出其重量的等级（W/R/B）；

保证没有环，也没有非法情况

思路：

如果能够确定一个物品的重量，那么这个物品一定处于一条长度为2的链子上，那么我们可以O（n）枚举个点，判断其是否在这个长度为2的链子的中间点上即可。

如果在的话，对应将这三个点都标上颜色，维护下去即可。

问题的小难点在于等号情况，其实这里我们只要将所有等号的部分都用并查集搞在一起即可，每一次加边我们都用并查集的祖先节点去代替就行。

Ac代码：

#include <bits/stdc++.h>
typedef long long int LL;
using namespace std;
const int MOD = 1e9+7;
void fre()
{
    freopen("INPUT.TXT","r",stdin);
    freopen("OUTPUT.TXT","w",stdout);
}
int ok;
char ans[1500];
int vis[1500];
int f[1500];
vector<int>mp[1500],re[1500];
int uu[1500*1500],vv[1500*1500],opp[1500*1500];
int find(int u)
{
    int r=u;
    while(r!=f[r])
    {
        r=f[r];
    }
    int i=u,j=r;
    while(i!=j)
    {
        j=f[i];
        f[i]=r;
        i=j;
    }
    return r;
}
int merge(int u,int v)
{
    int uu=find(u);
    int vv=find(v);
    if(uu!=vv)
    {
        f[uu]=vv;
    }
}
int main()
{
    fre();
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)f[i]=i;
    for(int i=1; i<=n; i++)mp[i].clear(),re[i].clear();
    for(int i=1; i<=m; i++)
    {
        char a[1500];
        scanf("%s",a);
        int len=strlen(a);
        int u=0,v=0,flag=0,op;
        for(int j=0; j<len; j++)
        {
            if(a[j]>='0'&&a[j]<='9'&&flag==0)
            {
                u=u*10+(a[j]-'0');
            }
            else if(a[j]>='0'&&a[j]<='9'&&flag==1)
            {
                v=v*10+(a[j]-'0');
            }
            else
            {
                if(a[j]=='>')op=1;
                if(a[j]=='<')op=2;
                if(a[j]=='=')op=3;
                flag++;
            }
        }
        if(op==3)
        {
            merge(u,v);
        }
        uu[i]=u;
        vv[i]=v;
        opp[i]=op;
    }
    for(int i=1;i<=m;i++)
    {
        int u=uu[i],v=vv[i],op=opp[i];
        if(opp[i]==3)continue;
        if(op==1)
        {
            u=find(u),v=find(v);
            mp[u].push_back(v);
            re[v].push_back(u);
        }
        if(op==2)
        {
            u=find(u),v=find(v);
            mp[v].push_back(u);
            re[u].push_back(v);
        }
    }
    memset(ans,'?',sizeof(ans));
    for(int i=1; i<=n; i++)
    {
        if(mp[i].size()>0&&re[i].size()>0)
        {
            ans[i]='R';
            for(int j=0; j<mp[i].size(); j++)
            {
                int v=mp[i][j];
                ans[v]='B';
            }
            for(int j=0; j<re[i].size(); j++)
            {
                int v=re[i][j];
                ans[v]='W';
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        if(f[i]==i)
        {
            for(int j=1; j<=n; j++)
            {
                if(i==j)continue;
                else if(find(j)==find(i))
                {
                    ans[j]=ans[i];
                }
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        printf("%c",ans[i]);
    }
    printf("\n");
}