Submission #666625

---

Source Code Expand

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class Main {
    private static int N;
    private static int A;
    private static int[] X;
    private static int[] Y;
    private static int B;
    private static int[] U;
    private static int[] V;
    private static Map<Integer, TreeSet<Integer>> C = new HashMap();
    private static Map<Integer, TreeSet<Integer>> C2 = new HashMap();
    private static TreeSet<Integer> T = new TreeSet();

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(in.readLine());
        for (int i = 1; i <= N; i++) {
            T.add(i);
        }
        A = Integer.parseInt(in.readLine());
        X = new int[A];
        Y = new int[A];
        for (int i = 0; i < A; i++) {
            String[] s = in.readLine().split(" ");
            X[i] = Integer.parseInt(s[0]);
            Y[i] = Integer.parseInt(s[1]);
            if (!C.containsKey(X[i])) {
                C.put(X[i], new TreeSet());
            }
            C.get(X[i]).add(Y[i]);
        }
        B = Integer.parseInt(in.readLine());
        U = new int[B];
        V = new int[B];
        for (int i = 0; i < B; i++) {
            String[] s = in.readLine().split(" ");
            U[i] = Integer.parseInt(s[0]);
            V[i] = Integer.parseInt(s[1]);
            if (!C2.containsKey(V[i])) {
                C2.put(V[i], new TreeSet());
            }
            C2.get(V[i]).add(U[i]);
        }
        int ans = 0;
        while (true) {
            boolean removed = false;
            for (Integer i : T) {
                if ((!C.containsKey(i) || C.get(i).size() == 0) && (!C2.containsKey(i) || C2.get(i).size() == 0)) {
                    T.remove(i);
                    C.remove(i);
                    C2.remove(i);
                    for (Map.Entry<Integer, TreeSet<Integer>> e : C.entrySet()) {
                        e.getValue().remove(i);
                    }
                    for (Map.Entry<Integer, TreeSet<Integer>> e : C2.entrySet()) {
                        e.getValue().remove(i);
                    }
                    ans++;
                    removed = true;
                    break;
                }
            }
            if (!removed) {
                if (C2.size() == 0) {
                    break;
                }
                int max = 0;
                int maxi = 0;
                for (Map.Entry<Integer, TreeSet<Integer>> e : C2.entrySet()) {
                    int k = e.getKey();
                    TreeSet<Integer> v = e.getValue();
                    if (max < v.size() + (C.containsKey(k) ? C.get(k).size() : 0)) {
                        max = v.size() + (C.containsKey(k) ? C.get(k).size() : 0);
                        maxi = k;
                    }
                }
                T.remove(maxi);
                C.remove(maxi);
                C2.remove(maxi);
                /**
                for (Map.Entry<Integer, TreeSet<Integer>> e : C.entrySet()) {
                    e.getValue().remove(maxi);
                }
                 **/
                for (Map.Entry<Integer, TreeSet<Integer>> e : C2.entrySet()) {
                    e.getValue().remove(maxi);
                }
            }
        }
        PrintWriter out = new PrintWriter(System.out);
        out.println(ans);
        out.flush();
    }
}

Submission Info

Compile Error

Note: ./Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Judge Result