NewOJ 2022 Contest 3 H题（字符串+Map+并查集+离散化/Hash）

题目链接

题目大意

现在给定一些变量的等于或者不等于的约束，请你判断这些约束能否同时满足。
输入时变量为x1,x2,…,xn，均以x开始，x后面为该变量对应的编号。
约束条件只有”=”或者”!=”。

说明

输入第一行为正整数T，表示存在T组测试数据。（T≤10）
每组测试数据第一行为正整数n，表示约束条件的数量。（n≤1000000）
接下来n行，每行以下列形式输出
xi = xj
xi != xj
其中i和j表示对应变量的编号。（1≤i,j≤10^9）
对于每组测试数据，输出一行Yes表示可以满足，输出No表示不能满足。

Input

2
4
x1 = x7
x9 != x7
x13 = x9
x1 = x13
2
x1 = x2
x2 = x1s

Output

No
Yes

思路

实现细节比较多，主要练练 Java, 注意 $1 <= i, j <= 10^9$ ， 所以要先离散化一下，用 Map 来映射

然后把所有相等的变量用并查集全都联通起来，然后查看不相等的变量是否在同一个连通块中, 如果出现矛盾输出 No, 否则 Yes

代码

import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;
import java.util.Arrays;

public class Main {
    private static final int N = 1000001;
    private static int[] x = new int[N];
    private static int[] y = new int[N];
    private static boolean[] z = new boolean[N];
    private static int[] fa = new int[N];
    private static int tot = 0;
    private static Map<Integer, Integer> mp = new HashMap<Integer, Integer>();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        while(T-- > 0) {
            mp.clear();
            Arrays.fill(x, 0);
            Arrays.fill(y, 0);
            Arrays.fill(z, false);
            tot = 0;
            for(int i = 1; i <= N - 1; i++) {
                fa[i] = i;
            }
            int n = in.nextInt();
            for(int i = 1; i <= n; i++) {
                String s = in.next();
                String mark = in.next();
                String t = in.next();
                for(int j = 1; j < s.length(); j++) {
                    x[i] = (s.charAt(j) - '0') + x[i] * 10;
                }
                for(int j = 1; j < t.length(); j++) {
                    y[i] = (t.charAt(j) - '0') + y[i] * 10;
                }
                /**
                 * 如果写 (mark == "=" )永远为假
                 * 必须写 mark.equals("=")
                 */
                if(mark.equals("=") ) {
                    //System.out.println("****");
                    z[i] = true;
                } else {
                    z[i] = false;
                }
            }
            for(int i = 1; i <= n; i++) {
                x[i] = get(x[i]);
                y[i] = get(y[i]);
            }
            solve(n);

        }
    }
    public static int Find(int x) {
        int y = x;
        while(y != fa[y]) {
            y = fa[y];
        }
        while(y != x) {
            int tmp = fa[x];
            fa[x] = y;
            x = tmp;
        }
        return y;
    }
    public static boolean Union(int x, int y) {
        x = Find(x);
        y = Find(y);
        if(x != y) {
            fa[y] = x;
            return true;
        }
        return false;
    }


    public static void solve(int n) {
        boolean fff = false;
        for(int i = 1; i <= n; i++) {
            if(z[i]) Union(x[i], y[i]);
        }
        for(int i = 1; i <= n; i++) {
            if(z[i] == false) {
                if(Find(x[i]) == Find(y[i])) fff = true;
            }
        }
        if(fff) {
            System.out.println("No");
        } else {
            System.out.println("Yes");
        }
    }

    /**
     * Hash/离散化过程
     */
    public static int get(int x) {
        if(mp.get(x) == null) {
            mp.put(x, ++tot);
        }
        //System.out.println(x + "--->" + mp.get(x));
        return mp.get(x);
    }
}