#include <cstdio> #include <unordered_set> #include <vector> using namespace std; int n,m,d; unordered_set <int> G[200100]; int kolor[200100]; vector <int> skladowe[200100]; int maxi=0; void usun(int poz) { if(G[poz].size()>0 && G[poz].size()<d) { for(unordered_set <int>::iterator i=G[poz].begin();i != G[poz].end();++i) { unordered_set <int>::iterator f=G[*i].find(poz); if(f!=G[poz].end()) { G[*i].erase(f); } } for(unordered_set <int>::iterator i=G[poz].begin();i != G[poz].end();++i) { usun(*i); } G[poz].clear(); } } void odnacz(int poz, int kol) { if(kolor[poz]!=0) return; kolor[poz]=kol; for(unordered_set <int>::iterator i=G[poz].begin();i != G[poz].end();++i) { odnacz(*i, kol); } } int main () { scanf("%d%d%d", &n,&m,&d); for(int i=0,a,b;i<m;++i) { scanf("%d%d", &a,&b); G[a-1].insert(b-1); G[b-1].insert(a-1); } for(int i=0;i<n;++i) { usun(i); } int kol=0; for(int i=0;i<n;++i) { if(kolor[i]==0) { ++kol; odnacz(i, kol); } } for(int i=0;i<n;++i) { skladowe[kolor[i]].push_back(i); if(skladowe[maxi].size() < skladowe[kolor[i]].size()) maxi=kolor[i]; } if(skladowe[maxi].size() == 1) { printf("NIE\n"); } else { printf("%d\n", skladowe[maxi].size()); for(int i=0;i<skladowe[maxi].size();++i) { printf("%d ", skladowe[maxi][i]+1); } printf("\n"); } }
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 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | #include <cstdio> #include <unordered_set> #include <vector> using namespace std; int n,m,d; unordered_set <int> G[200100]; int kolor[200100]; vector <int> skladowe[200100]; int maxi=0; void usun(int poz) { if(G[poz].size()>0 && G[poz].size()<d) { for(unordered_set <int>::iterator i=G[poz].begin();i != G[poz].end();++i) { unordered_set <int>::iterator f=G[*i].find(poz); if(f!=G[poz].end()) { G[*i].erase(f); } } for(unordered_set <int>::iterator i=G[poz].begin();i != G[poz].end();++i) { usun(*i); } G[poz].clear(); } } void odnacz(int poz, int kol) { if(kolor[poz]!=0) return; kolor[poz]=kol; for(unordered_set <int>::iterator i=G[poz].begin();i != G[poz].end();++i) { odnacz(*i, kol); } } int main () { scanf("%d%d%d", &n,&m,&d); for(int i=0,a,b;i<m;++i) { scanf("%d%d", &a,&b); G[a-1].insert(b-1); G[b-1].insert(a-1); } for(int i=0;i<n;++i) { usun(i); } int kol=0; for(int i=0;i<n;++i) { if(kolor[i]==0) { ++kol; odnacz(i, kol); } } for(int i=0;i<n;++i) { skladowe[kolor[i]].push_back(i); if(skladowe[maxi].size() < skladowe[kolor[i]].size()) maxi=kolor[i]; } if(skladowe[maxi].size() == 1) { printf("NIE\n"); } else { printf("%d\n", skladowe[maxi].size()); for(int i=0;i<skladowe[maxi].size();++i) { printf("%d ", skladowe[maxi][i]+1); } printf("\n"); } } |