3.9美团笔试第五题【java】不用离散化的版本

import java.util.*;
import java.io.*;

public class Main {
    public static class Pair{
        public int op;
        public int u;
        public int v;
        public Pair(int s,int l){
            u=s<l?s:l;
            v=u==s?l:s;
        }
        public Pair(int op, int s, int l) {
            this(s,l);
            this.op = op;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair pair = (Pair) o;
            return op == pair.op && u == pair.u && v == pair.v;
        }

        @Override
        public int hashCode() {
            return Objects.hash(op, u, v);
        }
    }
    static HashSet<Pair> fr=new HashSet<>();

    static ArrayList<Pair> qs=new ArrayList<>(1<<20);
    static ArrayList<String> ans=new ArrayList<>(1<<20);
    static HashMap<Integer,Integer> father=new HashMap<>();
    static HashMap<Integer,Integer> size=new HashMap<>();
    static ArrayList<Integer> help=new ArrayList<>();
    public static void main(String[] args) throws Exception {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
        st.nextToken();
        int n = (int) st.nval;
        st.nextToken();
        int m = (int) st.nval;
        st.nextToken();
        int q = (int) st.nval;
        while(m--!=0){
            st.nextToken();
            int u = (int) st.nval;
            st.nextToken();
            int v = (int) st.nval;
            fr.add(new Pair(u,v));
        }
        while(q--!=0){
            st.nextToken();
            int op = (int) st.nval;
            st.nextToken();
            int u = (int) st.nval;
            st.nextToken();
            int v = (int) st.nval;
            if(op==1){
                if(fr.remove(new Pair(u,v)))
                    qs.add(new Pair(op,u,v));
            } else{
                qs.add(new Pair(op,u,v));
            }
        }
        for (Pair pair : fr) {
            union(pair);
        }
        for (int i = qs.size() - 1; i >= 0; i--) {
            Pair pair=qs.get(i);
            if(pair.op==2){
                if(!find(pair.u).equals(find(pair.v)))   //Integer之间用equals
                    ans.add("No");
                else
                    ans.add("Yes");
            }else{
                union(pair);
            }
        }
        for (int i = ans.size() - 1; i >= 0; i--) {
            pw.println(ans.get(i));
        }
        pw.close();
    }

    private static void union(Pair pair) {
        int u=pair.u,v= pair.v;
        int fu=find(u);   //*********
        int fv=find(v);
        if(fu!=fv){
            Integer usize = size.getOrDefault(fu, 1);
            Integer vsize = size.getOrDefault(fv, 1);
            if(usize <= vsize) {
                father.put(fu, fv);
                size.put(fv,usize+vsize);
                size.remove(fu);
            } else{
                father.put(fv, fu);
                size.put(fu,usize+vsize);
                size.remove(fv);
            }
        }
    }

    private static Integer find(int u) {
        help.clear();
        while(father.getOrDefault(u,u)!=u){  //************
            help.add(u);
            u=father.get(u);
        }
        for (Integer i : help) {
            father.put(i,u);
        }
        return u;
    }
}