算法分析

并查集

• 1、题目的数组大小最高有$10^9$，可我们用到的只有 $2 * 10^6$ ,数据相差过大，因此需要用不要求保序的离散化(哈希表)对数据进行处理，将数据中的值映射成 $1$ 到 $2 * 10^6$

• 2、先将所有相等的条件进行合并，形成一个集合体

• 3、将所有不等条件进行判断处理，若a != b，而a和b却在同一集合，存在矛盾

注意：需要实现用结构体存储所有的条件，1表示相等，0表示不等

时间复杂度$O(n)$

并查集操作接近$O(1)$

参考文献

算法提高课

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
public class Main {
    static int N = 2000010; 
    static int n,k;
    static Edge[] edge = new Edge[N];
    static Map<Integer,Integer> S = new HashMap<Integer,Integer>();
    static int[] p = new int[N];
    static int get(int x)
    {
        if(!S.containsKey(x)) S.put(x, ++ k);
        return S.get(x);
    }
    static int find(int x)
    {
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while(T -- > 0)
        {
            n = Integer.parseInt(br.readLine());
            k = 0;
            S.clear();
            for(int i = 0;i < n;i ++)
            {
                String[] s1 = br.readLine().split(" ");
                int a = Integer.parseInt(s1[0]);
                int b = Integer.parseInt(s1[1]);
                int c = Integer.parseInt(s1[2]);
                edge[i] = new Edge(get(a),get(b),c);
            }

            for(int i = 1;i <= k;i ++) p[i] = i;//注意：这里循环到k，表示有k个点
            //合并所有相等约束条件
            for(int i = 0;i < n;i ++)
            {
                if(edge[i].c == 1)
                {
                    int pa = find(edge[i].a);
                    int pb = find(edge[i].b);
                    if(pa != pb)
                    {
                        p[pa] = pb;
                    }
                }

            }
            boolean flag = false;//判断是否冲突
            //判断所有不相等约束
            for(int i = 0;i < n;i ++)
            {
                if(edge[i].c == 0)
                {
                    int pa = find(edge[i].a);
                    int pb = find(edge[i].b);
                    if(pa == pb)
                    {
                        flag = true;
                        break;
                    }
                }
            }
            if(flag) System.out.println("NO");
            else System.out.println("YES");
        }



    }
}
class Edge
{
    int a,b,c;
    Edge(int a,int b,int c)
    {
        this.a = a;
        this.b = b;
        this.c = c;
    }
}