题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;

const int N = 2000010;

struct query{
    int a, b, type;
} query[N];
int p[N];
unordered_map<int, int> h;
int cnt, n;

int find(int x)
{
    if (x != p[x])  p[x] = find(p[x]);
    return p[x];
}
int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        scanf("%d", &n);
        cnt = 0;
        h.clear();
        for (int i = 0; i < n; i ++)
        {
            int a, b, e;
            scanf("%d%d%d", &a, &b, &e);

            if (!h.count(a)) h[a] = ++ cnt;
            if (!h.count(b)) h[b] = ++ cnt;

            query[i] = {h[a], h[b], e};
        }

        for (int i = 1; i <= cnt; i ++) p[i] = i;

        for (int i = 0; i < n; i ++)
            if (query[i].type == 1)
                p[find(query[i].a)] = find(query[i].b);

        bool flag = true;
        for (int i = 0; i < n; i ++)
        {
            if (query[i].type == 0 && find(query[i].a) == find(query[i].b))
            {
                flag = false;
                break;
            }
        }

        if (flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla