NCSTOJ-1403 : 等式

拼搏现实的明天。 2022-03-02 07:22 152阅读 0赞

# [1403 : 等式][1403 _] #

### Description ###

n个变量和m个“相等”或“不相等”的约束条件，请你判定是否存在一种赋值方案满足所有m个约束条件。

### Input ###

第一行一个整数T，表示数据组数。(T<=100)  
接下来会有T组数据，对于每组数据：  
第一行是两个整数n,m，表示变量个数和约束条件的个数。(1<=n,m<=500000)  
接下来m行，每行三个整数a,b,e(1<=a,b<=n)，表示第a个变量和第b个变量的关系：

*  若e=0则表示第a个变量不等于第b个变量；
 *  若e=1则表示第a个变量等于第b个变量  
    保证所有数据的n总和不超过500000。

### Output ###

输出T行，第i行表示第i组数据的答案。若第i组数据存在一种方案则输出"Yes"；否则输出"No"（不包括引号）。

### Sample Input ###

2
    5 5
    1 2 1
    2 3 1
    3 4 1
    1 4 1
    2 5 0
    3 3
    1 2 1
    2 3 1
    1 3 0

### Sample Output ###

Yes
    No

### 并查集 ###

#include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <string>
    #include <cstring>
    #include <unordered_set>
    #include <set>
    #include <unordered_map>
    #include <vector>
    #include <algorithm>
    #include <set>
    #include <queue>
    #include <cmath>
    using namespace std;
    int n, m;         // n个变量，m个条件
    vector<int> nums; //相等的变量
    vector<int> ranks;
    int findroot(int x)
    { 
        if (x == nums[x])
            return x;
        return nums[x] = findroot(nums[x]);
    }
    bool checkSame(int x, int y)
    { 
        return findroot(x) == findroot(y);
    }
    void init() //初始化
    { 
        for (int i = 1; i <= 2 * n; i++)
        { 
            nums[i] = i;
        }
    }
    void merge(int x, int y)
    { 
        int dx = findroot(x);
        int dy = findroot(y);
        if (dx == dy)
            return;
        if(ranks[dx]<ranks[dy]) 
            nums[dx]=dy;
        else
        { 
            if(ranks[dx]==ranks[dy])
                ranks[dx]++;
            nums[dy]=dx;
        }
    }
    int main()
    { 
        // freopen("5.txt","r",stdin);
        int t;
        scanf("%d",&t);
        while (t--)
        { 
            scanf("%d%d",&n,&m);
            nums.assign(2 * n+1,0);
            ranks.assign(2 * n+1,0);
            int u, v, k;
            bool flag = true;
            init();
            for (int i = 0; i < m; i++)
            { 
                scanf("%d%d%d",&u,&v,&k);
                if (flag) //这里设置flag是为了，当已经有不满足条件的情况时，后面的就不必再判断，降低时间复杂度
                {  
                    if (k == 1) //表示u,v变量相等
                    { 
                        if (checkSame(u,v+n) || checkSame(u+n,v)) //考虑变量不相等情况
                        { 
                            flag = false;
                        }
                        else //表示不等
                        { 
                            merge(u, v);
                            merge(u + n, v + n);
                        }
                    }
                    else if (k == 0) //表示两个变量不相等
                    { 
                        if (checkSame(u,v) || checkSame(u+n,v+n)) //考虑变量相等情况
                        { 
                            flag = false;
                        }
                        else
                        { 
                            merge(u + n, v);
                            merge(u, v + n);
                        }
                    }
                }
            }
            if (flag)
                printf("Yes\n");
            else
                printf("No\n");
        }
        return 0;
    }

[1403 _]: http://acm.ncst.edu.cn/problem.php?pid=1403