Proficient.
Put your skills to the test.

Problem summary

Count direct roads incident to each city, including parallel roads. Output cities incident to at least K roads.

Constraints

N ≤ 10000 cities; labels ≤ P ≤ 10^9; M ≤ 100000; 1 ≤ K ≤ 10000.

Worked example

An independently prepared example for this explanation.

6 7
1 2
1 4
2 3
2 4
2 5
3 4
3 6
3

3
2 3 4

Solution analysis

1. Only cities that occur in a road can meet the positive threshold. Store incident-road counts in an ordered map indexed by the sparse city labels.
2. For every input road increment both endpoint counts. Parallel roads count independently, so do not remove duplicate endpoint pairs. Filter entries with count at least K.
3. In the sample, cities 2,3,4 have degrees 4,3,3. City 1 has degree 2, while 5 and 6 have degree 1. Threshold 3 therefore gives 2 3 4.

Why it works

Each road contributes exactly one to the degree of each of its two endpoints. After all increments every stored count is the required number of outgoing roads. Filtering by K selects exactly the hubs, and map order supplies ascending labels.

Watch out. Do not allocate P entries: P can be a billion. Parallel roads affect the degree.

An independently written complete program with standard headers.

#include<iostream>
#include<map>
#include<vector>
// Algorithm: Only cities that occur in a road can meet the positive threshold.
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int p,m;
    cin>>p>>m;
    map<int,int>degree;
    for(int i=0;i<m;++i){
        int a,b;
        cin>>a>>b;
        ++degree[a];
        ++degree[b];
    }
    int threshold;
    cin>>threshold;
    vector<int>hubs;
    for(const auto&entry:degree){
        if(entry.second>=threshold){
            hubs.push_back(entry.first);
        }
    }
    cout<<hubs.size()<<'\n';
    for(int i=0;i<static_cast<int>(hubs.size());++i){
        if(i>0){
            cout<<' ';
        }
        cout<<hubs[i];
    }
    if(!hubs.empty()){
        cout<<'\n';
    }
}