#include<bits/stdc++.h> #define rep(i,k,n) for(int i= (int) k;i< (int) n;i++) #define pb push_back #define ft first #define sd second typedef long long ll; const long long inf = 9223372036854775807ll; const int iinf = 2147483647; const int limit = 1048576; using namespace std; bool sync_with_stdio (bool sync = false); void dfs(ll v, vector<ll>& cand, vector<bool>& removed, const vector<vector<ll> >& nei) { removed[v] = true; cand.pb(v); rep(i, 0, nei[v].size()) if(!removed[nei[v][i]]) dfs(nei[v][i], cand, removed, nei); } int main(){ ll n, m, d; scanf("%lld%lld%lld", &n, &m, &d); vector<ll> degs(n + 1, 0); vector<vector<ll> > nei(n + 1); ll t1, t2; rep(i, 0, m) { scanf("%lld%lld", &t1, &t2); nei[t1].pb(t2); nei[t2].pb(t1); degs[t1]++; degs[t2]++; } priority_queue<pair<ll, ll>, vector<pair<ll, ll> >, greater<pair<ll, ll> > > cities; rep(i, 1, n + 1) cities.push({degs[i], i}); vector<bool> removed(n + 1, 0); while(cities.size() && (cities.top().ft < d || removed[cities.top().sd])) { ll city = cities.top().sd; cities.pop(); if(!removed[city]) rep(i, 0, nei[city].size()) { degs[nei[city][i]]--; cities.push({degs[nei[city][i]], nei[city][i]}); } removed[city] = true; } vector<ll> cand; rep(i, 1, n + 1) { vector<ll> new_cand; if(!removed[i]) dfs(i, new_cand, removed, nei); if(new_cand.size() > cand.size()) swap(new_cand, cand); } if(cand.size()) { sort(cand.begin(), cand.end()); printf("%d\n", cand.size()); rep(i, 0, cand.size()) printf("%lld ", cand[i]); } else printf("NIE"); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | #include<bits/stdc++.h> #define rep(i,k,n) for(int i= (int) k;i< (int) n;i++) #define pb push_back #define ft first #define sd second typedef long long ll; const long long inf = 9223372036854775807ll; const int iinf = 2147483647; const int limit = 1048576; using namespace std; bool sync_with_stdio (bool sync = false); void dfs(ll v, vector<ll>& cand, vector<bool>& removed, const vector<vector<ll> >& nei) { removed[v] = true; cand.pb(v); rep(i, 0, nei[v].size()) if(!removed[nei[v][i]]) dfs(nei[v][i], cand, removed, nei); } int main(){ ll n, m, d; scanf("%lld%lld%lld", &n, &m, &d); vector<ll> degs(n + 1, 0); vector<vector<ll> > nei(n + 1); ll t1, t2; rep(i, 0, m) { scanf("%lld%lld", &t1, &t2); nei[t1].pb(t2); nei[t2].pb(t1); degs[t1]++; degs[t2]++; } priority_queue<pair<ll, ll>, vector<pair<ll, ll> >, greater<pair<ll, ll> > > cities; rep(i, 1, n + 1) cities.push({degs[i], i}); vector<bool> removed(n + 1, 0); while(cities.size() && (cities.top().ft < d || removed[cities.top().sd])) { ll city = cities.top().sd; cities.pop(); if(!removed[city]) rep(i, 0, nei[city].size()) { degs[nei[city][i]]--; cities.push({degs[nei[city][i]], nei[city][i]}); } removed[city] = true; } vector<ll> cand; rep(i, 1, n + 1) { vector<ll> new_cand; if(!removed[i]) dfs(i, new_cand, removed, nei); if(new_cand.size() > cand.size()) swap(new_cand, cand); } if(cand.size()) { sort(cand.begin(), cand.end()); printf("%d\n", cand.size()); rep(i, 0, cand.size()) printf("%lld ", cand[i]); } else printf("NIE"); return 0; } |