#include <cstdio> #include <set> #include <vector> #include <string> #include <map> #include <algorithm> using namespace std; int n, m, d, a, b; set<int> tab[200040]; struct lex_compare { bool operator() (const int& lhs, const int& rhs) const{ if(tab[lhs].size()==tab[rhs].size()){ return lhs<rhs; } return tab[lhs].size()<tab[rhs].size(); } }; bool visited[200400]; bool visited2[200400]; bool cmp(int i,int j) { return (i<j); } int main(){ scanf("%d %d %d", &n, &m, &d); for(int i=0; i<m; i++){ scanf("%d %d", &a, &b); tab[a].insert(b); tab[b].insert(a); } set<int, lex_compare> s; for(int i=1;i<=n; i++){s.insert(i);} while(!s.empty()){ int it = *(s.begin()); if(tab[it].size()<d){ s.erase(it); for(set<int>::iterator ii = tab[it].begin(); ii!=tab[it].end(); ii++){ int p=*ii; s.erase(p); tab[p].erase(it); s.insert(p); } tab[it].clear(); }else{ break; } } if(s.empty()){ printf("NIE\n"); return 0; } int max_number_of_vertices=-1; int vertex_number=-1; for(int i=1; i<=n; i++){ vector<int> v; if(!visited[i]){ visited[i]=1; int counter=1; v.push_back(i); for(int j=0; j<v.size(); j++){ int y=v[j]; for(set<int>::iterator ii = tab[y].begin(); ii!=tab[y].end(); ii++){ if(!visited[*ii]){ visited[*ii]=1; counter++; v.push_back(*ii); } } } if(counter>max_number_of_vertices){ max_number_of_vertices=counter; vertex_number=i; } } } vector<int> wynik; wynik.push_back(vertex_number); visited2[vertex_number]=1; for(int j=0; j<wynik.size(); j++){ int y=wynik[j]; for(set<int>::iterator ii = tab[y].begin(); ii!=tab[y].end(); ii++){ if(!visited2[*ii]){ visited2[*ii]=1; wynik.push_back(*ii); } } } sort(wynik.begin(), wynik.end(), cmp); printf("%d\n", max_number_of_vertices); for(int i=0; i<wynik.size(); i++){ printf("%d ", wynik[i]); } printf("\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 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 | #include <cstdio> #include <set> #include <vector> #include <string> #include <map> #include <algorithm> using namespace std; int n, m, d, a, b; set<int> tab[200040]; struct lex_compare { bool operator() (const int& lhs, const int& rhs) const{ if(tab[lhs].size()==tab[rhs].size()){ return lhs<rhs; } return tab[lhs].size()<tab[rhs].size(); } }; bool visited[200400]; bool visited2[200400]; bool cmp(int i,int j) { return (i<j); } int main(){ scanf("%d %d %d", &n, &m, &d); for(int i=0; i<m; i++){ scanf("%d %d", &a, &b); tab[a].insert(b); tab[b].insert(a); } set<int, lex_compare> s; for(int i=1;i<=n; i++){s.insert(i);} while(!s.empty()){ int it = *(s.begin()); if(tab[it].size()<d){ s.erase(it); for(set<int>::iterator ii = tab[it].begin(); ii!=tab[it].end(); ii++){ int p=*ii; s.erase(p); tab[p].erase(it); s.insert(p); } tab[it].clear(); }else{ break; } } if(s.empty()){ printf("NIE\n"); return 0; } int max_number_of_vertices=-1; int vertex_number=-1; for(int i=1; i<=n; i++){ vector<int> v; if(!visited[i]){ visited[i]=1; int counter=1; v.push_back(i); for(int j=0; j<v.size(); j++){ int y=v[j]; for(set<int>::iterator ii = tab[y].begin(); ii!=tab[y].end(); ii++){ if(!visited[*ii]){ visited[*ii]=1; counter++; v.push_back(*ii); } } } if(counter>max_number_of_vertices){ max_number_of_vertices=counter; vertex_number=i; } } } vector<int> wynik; wynik.push_back(vertex_number); visited2[vertex_number]=1; for(int j=0; j<wynik.size(); j++){ int y=wynik[j]; for(set<int>::iterator ii = tab[y].begin(); ii!=tab[y].end(); ii++){ if(!visited2[*ii]){ visited2[*ii]=1; wynik.push_back(*ii); } } } sort(wynik.begin(), wynik.end(), cmp); printf("%d\n", max_number_of_vertices); for(int i=0; i<wynik.size(); i++){ printf("%d ", wynik[i]); } printf("\n"); return 0; } |