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> map_ren=new HashMap<>();
    static int[] f=new int[200010];
    static int[] size=new int[200010];
    static int[] help=new int[200010];
    public static  void init(){
        for (int i = 0; i < 200010; i++) {
            f[i]=i;
            size[i]=1;
        }
    }
    public static void main(String[] args) throws Exception {
        init();
        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;
        int id=1;
        while(m--!=0){
            st.nextToken();
            int u = (int) st.nval;
            if(map_ren.get(u)==null)map_ren.put(u,id++);
            st.nextToken();
            int v = (int) st.nval;
            if(map_ren.get(v)==null)map_ren.put(v,id++);
            Integer mu=map_ren.get(u);
            Integer mv=map_ren.get(v);
            fr.add(new Pair(mu,mv));
        }
        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(map_ren.get(u)==null)map_ren.put(u,id++);
            if(map_ren.get(v)==null)map_ren.put(v,id++);
            Integer mu=map_ren.get(u);
            Integer mv=map_ren.get(v);
            f[mu]=mu;
            f[mv]=mv;
            if(op==1){
                    if(fr.remove(new Pair(mu,mv)))
                        qs.add(new Pair(op,mu,mv));
            } else{
                qs.add(new Pair(op,mu,mv));
            }
        }
        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)!=find(pair.v))
                    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),fv=find(v);
        if(fu!=fv){
            int sfu=size[fu];
            int sfv=size[fv];
            if(sfu<=sfv){
                f[fu]=fv;
                size[fv]=sfv+sfu;
            } else{
                f[fv]=fu;
                size[fu]=sfv+sfu;
            }
        }
    }

    private static int find(int u) {
        int top=0;
        while(f[u]!=u){
            help[top++]=u;
            u=f[u];
        }
        while(top!=0){
            f[help[--top]]=u;
        }
        return u;
    }
}