美团3.12笔试第三题

#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
private:
 static bool cmp(const vector<int>& a, const vector<int>& b) {
  return a[2] < b[2];
 }
public:
 int getRes(int m, vector<vector<int>>& nums) {
  int n = nums.size();
  vector<int> dishes(m, 1);
  unordered_map<int, int> dishCnt;
  for (int i = 0; i < nums.size(); i++) {
   dishCnt[nums[i][0]]++;
   dishCnt[nums[i][1]]++;
  }
  vector<vector<int>> priorities(n, vector<int>(3, 0));
  for (int i = 0; i < n; i++) {
   priorities[i][0] = nums[i][0];
   priorities[i][1] = nums[i][1];
   priorities[i][2] = dishCnt[nums[i][0]] + dishCnt[nums[i][1]];
  }
  sort(priorities.begin(), priorities.end(), cmp);
  int res = 0;
  for (int i = 0; i < n; i++) {
   int dish1 = priorities[i][0], dish2 = priorities[i][1];
   if (dishes[dish1 - 1] == 0 || dishes[dish2 - 1] == 0) {
    continue;
    //break;
   }
   dishes[dish1 - 1] = 0;
   dishes[dish2 - 1] = 0;
   res++;
  }
  return res;
 }
};

int main() {
 int m, n;
 while (cin >> m >> n) {
  vector<vector<int>> nums(n, vector<int>(2));
  for (int i = 0; i < n; i++) {
   cin >> nums[i][0] >> nums[i][1];
  }
  Solution Sol;
  int res = Sol.getRes(m, nums);
  cout << res << endl;
 }
 return 0;
}