#include <iostream> #include <algorithm> #include <queue> #include <vector> using namespace std; int const N = 2*1e5+5; vector <int> G[N]; int Deg[N] = {0}; queue <int > Q; int main (){ ios_base::sync_with_stdio(0); int n,m,d; cin>>n>>m>>d; vector <int> visited(n+1); for (int i=0;i<m;i++){ int a,b; cin >> a>> b; G[a].push_back(b); G[b].push_back(a); Deg[a]++; Deg[b]++; } for (int i=1;i<=n;i++){ if (G[i].size() < d) Q.push(i); } int ad = 0; while (!Q.empty()){ int a = Q.front(); Q.pop(); ad++; for (int i=0;i<G[a].size();i++){ if (Deg[G[a][i] ] == d)Q.push(G[a][i]); Deg[G[a][i] ]--; } } if (ad == n)cout<<"NIE"<<endl; else { int maxsize = 0; int sizeofthis = 0; int maxii = 0; for (int i =1;i<=n;i++){ sizeofthis = 0; if (Deg[i]<d)continue; if (visited[i]) continue; Q.push(i); //T[i].push_back(i); visited[i]=i; sizeofthis++; while (!Q.empty()){ int a = Q.front(); Q.pop(); for (int j=0;j<G[a].size();j++){ int k = G[a][j]; if (Deg[k]<d)continue; if (visited[k]) continue; Q.push(k); visited[k]=i; sizeofthis++; } } if (maxsize < sizeofthis)maxii = i; maxsize = max(maxsize,sizeofthis); } cout<<maxsize<<endl; for (int i =1;i<=n;i++) { if (visited[i] == maxii){ cout<< i<<" "; } } } }
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 69 70 71 72 73 74 75 76 77 78 79 | #include <iostream> #include <algorithm> #include <queue> #include <vector> using namespace std; int const N = 2*1e5+5; vector <int> G[N]; int Deg[N] = {0}; queue <int > Q; int main (){ ios_base::sync_with_stdio(0); int n,m,d; cin>>n>>m>>d; vector <int> visited(n+1); for (int i=0;i<m;i++){ int a,b; cin >> a>> b; G[a].push_back(b); G[b].push_back(a); Deg[a]++; Deg[b]++; } for (int i=1;i<=n;i++){ if (G[i].size() < d) Q.push(i); } int ad = 0; while (!Q.empty()){ int a = Q.front(); Q.pop(); ad++; for (int i=0;i<G[a].size();i++){ if (Deg[G[a][i] ] == d)Q.push(G[a][i]); Deg[G[a][i] ]--; } } if (ad == n)cout<<"NIE"<<endl; else { int maxsize = 0; int sizeofthis = 0; int maxii = 0; for (int i =1;i<=n;i++){ sizeofthis = 0; if (Deg[i]<d)continue; if (visited[i]) continue; Q.push(i); //T[i].push_back(i); visited[i]=i; sizeofthis++; while (!Q.empty()){ int a = Q.front(); Q.pop(); for (int j=0;j<G[a].size();j++){ int k = G[a][j]; if (Deg[k]<d)continue; if (visited[k]) continue; Q.push(k); visited[k]=i; sizeofthis++; } } if (maxsize < sizeofthis)maxii = i; maxsize = max(maxsize,sizeofthis); } cout<<maxsize<<endl; for (int i =1;i<=n;i++) { if (visited[i] == maxii){ cout<< i<<" "; } } } } |