#include<bits/stdc++.h> using namespace std; vector<int> tos[200001]; int st[200001]; int main(){ int n, m, d; scanf("%d%d%d", &n, &m, &d); for(int i=0;i<m;++i){ int a, b; scanf("%d%d", &a, &b); --a;--b; tos[a].push_back(b); tos[b].push_back(a); ++st[a]; ++st[b]; } priority_queue<pair<int, int> > q; for(int i=0;i<n;++i)q.push(make_pair(-st[i], i)); while(!q.empty()){ pair<int, int> t; t=q.top(); q.pop(); if(st[t.second]==-1)continue; t.first=-t.first; if(t.first<d){ st[t.second]=-1; for(int i=0;i<tos[t.second].size();++i){ --st[tos[t.second][i]]; if(st[tos[t.second][i]]<d && st[tos[t.second][i]]>-1) q.push(make_pair(-st[tos[t.second][i]], tos[t.second][i])); } } } vector<int> wyn; for(int j=0;j<n;++j){ queue<int> q2; q2.push(j); vector<int> aw; if(st[j]>0) while(!q2.empty()){ int t; t=q2.front(); q2.pop(); if(st[t]<1)continue; st[t]=0; aw.push_back(t); for(int i=0;i<tos[t].size();++i){ if(st[tos[t][i]]>0){ q2.push(tos[t][i]); } } } if(aw.size()>wyn.size())wyn.swap(aw); aw.clear(); } if(wyn.size()!=0){ printf("%d\n", wyn.size()); for(int i=0;i<wyn.size();++i){ printf("%d ", wyn[i]+1); } } else printf("NIE\n"); 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 69 70 71 72 73 | #include<bits/stdc++.h> using namespace std; vector<int> tos[200001]; int st[200001]; int main(){ int n, m, d; scanf("%d%d%d", &n, &m, &d); for(int i=0;i<m;++i){ int a, b; scanf("%d%d", &a, &b); --a;--b; tos[a].push_back(b); tos[b].push_back(a); ++st[a]; ++st[b]; } priority_queue<pair<int, int> > q; for(int i=0;i<n;++i)q.push(make_pair(-st[i], i)); while(!q.empty()){ pair<int, int> t; t=q.top(); q.pop(); if(st[t.second]==-1)continue; t.first=-t.first; if(t.first<d){ st[t.second]=-1; for(int i=0;i<tos[t.second].size();++i){ --st[tos[t.second][i]]; if(st[tos[t.second][i]]<d && st[tos[t.second][i]]>-1) q.push(make_pair(-st[tos[t.second][i]], tos[t.second][i])); } } } vector<int> wyn; for(int j=0;j<n;++j){ queue<int> q2; q2.push(j); vector<int> aw; if(st[j]>0) while(!q2.empty()){ int t; t=q2.front(); q2.pop(); if(st[t]<1)continue; st[t]=0; aw.push_back(t); for(int i=0;i<tos[t].size();++i){ if(st[tos[t][i]]>0){ q2.push(tos[t][i]); } } } if(aw.size()>wyn.size())wyn.swap(aw); aw.clear(); } if(wyn.size()!=0){ printf("%d\n", wyn.size()); for(int i=0;i<wyn.size();++i){ printf("%d ", wyn[i]+1); } } else printf("NIE\n"); return 0; } |