JD 8.24 笔试

考试安排：下来重新做了一遍
题目描述：
某校在积极推行无人监考制度，但是总有学生是不自觉的，
如果将两个很熟的异性朋友放在同一个考场里，他们就会
交流甚至作弊。因此一个考场中不能允许两个很熟的异性
朋友存在，学校希望通过搬出一部分学生的方法来改善这
一问题。
但是又因为教室数量有限，因此希望一个教室中容下的学
生尽可能多，即需要搬出教室的学生数量尽可能少，请你
输出搬出教室人数最少，且字典序最小的方案。
输入
输入第一行有两个整数n和m，分别表示有n个男生和n个
女生，有m个朋友关系。
(1<=n<=500,1<=m<=100000)
接下来m行，每行有两个整数，x和y，表示第x号男生
和第y号女生是朋友。男生的编号均为[1,n]，女生的
编号为[n+1,2n]。
输出
输出第一行包含一个整数a，表示最少需要搬出教室的人数。
输出第二行有a个整数，即a个需要搬出教室的人的编号，
要求人数最少，且字典序最小。

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Solution2 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){

            int n = in.nextInt();

            int m = in.nextInt();

            boolean[][] relationShips = new boolean[2*n+1][2*n+1];
            Cell[] cells = new Cell[2*n+1];
            PriorityQueue maxHeap = new PriorityQueue(new Comparator() {
                @Override
                public int compare(Cell o1, Cell o2) {
                    if(o1.count==o2.count){
                        return o1.no - o2.no;
                    }
                    return o2.count - o1.count;
                }
            });
            int count = 0;
            for (int i = 1; i <= m; i++) {

                int x = in.nextInt();

                int y = in.nextInt();

                relationShips[x][y] = true;
                relationShips[y][x] = true;

                count = count + 2;

                if(cells[x]==null){
                    cells[x] = new Cell(x);
                    cells[x].count = 1;
                }else{
                    cells[x].count++;
                }
                if(cells[y]==null){
                    cells[y] = new Cell(y);
                    cells[y].count = 1;
                }else{
                    cells[y].count++;
                }
            }

            for (int i = 1; i < cells.length; i++) {
                if(cells[i]!=null&&cells[i].count!=0)
                maxHeap.offer(cells[i]);
            }
            ArrayList ans = new ArrayList();
            while (count>0){
                Cell cell = maxHeap.poll();
                if(cell==null || cell.count==0) continue;

                count -= cell.count;

                int no = cell.no;
                for (int i = 1; i <= 2*n; i++) {
                    if(relationShips[no][i]){
                        relationShips[no][i]=false;
                        relationShips[i][no]=false;
                        cells[i].count--;
                        count--;
                    }
                }
                ans.add(no);

            }
            int num = ans.size();
            System.out.println(num);
            int[] out = new int[num];
            for (int i = 0; i < ans.size(); i++) {
                out[i] = ans.get(i);
            }
            for (int i = 0; i < out.length; i++) {
                if(i==0){
                    System.out.print(out[i]);
                }else {
                    System.out.print(" " + out[i]);
                }
            }
        }
    }
}
class Cell{
    int no;
    int count;
    Cell(int no){
        this.no = no;
        this.count = 0;
    }
}