【題解】ZeroJudeg c426: pE 網路測試的難題

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

int t, n, m, a, b, cnt[500005], mx;
vector <int> v[500005];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while (t--){
        cin >> n >> m;
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; i++){
            v[i].clear();
        }
        for (int i = 0; i < m; i++){
            cin >> a >> b;
            v[a].push_back(b);
            v[b].push_back(a);
            if (a < b) cnt[a]++;
            else cnt[b]++;
        }
        priority_queue <pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
        mx = 0;
        for (int i = 0; i < n; i++){
            mx = max(mx, cnt[i]);
            cnt[i] = v[i].size();
            pq.push({cnt[i], i});
        }
        cout << mx << " ";
        mx = 0;
        while (!pq.empty()){
            pair<int, int> now = pq.top();
            pq.pop();
            if (cnt[now.second] == -1) continue;
            mx = max(mx, now.first);
            cnt[now.second] = -1;
            for (auto i:v[now.second]){
                if (cnt[i] == -1) continue;
                cnt[i]--;
                pq.push({cnt[i], i});
            }
        }
        cout << mx << "\n";
    }
}