#include <cstdio> #include <vector> using namespace std; int main() { int n, m, d, x, y; scanf("%d %d %d\n", &n, &m, &d); vector<int> nr_roads(n+1); vector<int> groups(n+1); vector< vector<int> > roads(n+1); for(int i=0; i<m; i++) { scanf("%d %d\n", &x, &y); nr_roads[x]++; roads[x].push_back(y); nr_roads[y]++; roads[y].push_back(x); } vector<int> to_delete; for(int i=1; i<=n; i++) { if(nr_roads[i] < d) { groups[i] = -1; to_delete.push_back(i); } } while(to_delete.size()) { x = to_delete.back(); to_delete.pop_back(); for(int i=0; i<roads[x].size(); i++) { nr_roads[roads[x].at(i)]--; if(nr_roads[roads[x].at(i)] == d-1) { groups[roads[x].at(i)] = -1; to_delete.push_back(roads[x].at(i)); } } } int best = 0, best_nr = 0, current = 0; vector<int> frontier; for(int i=1; i<=n; i++) { if(groups[i] == 0) { groups[i] = i; current++; frontier.push_back(i); } while(frontier.size()) { x = frontier.back(); frontier.pop_back(); for(int j=0; j<roads[x].size(); j++) { if(groups[roads[x].at(j)] == 0) { groups[roads[x].at(j)] = i; current++; frontier.push_back(roads[x].at(j)); } } } if(current > best) { best = current; best_nr = i; } current = 0; } if(!best) printf("NIE\n"); else { printf("%d\n", best); for(int i=1; i<=n; i++) { if(groups[i] == best_nr) printf("%d ", 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 | #include <cstdio> #include <vector> using namespace std; int main() { int n, m, d, x, y; scanf("%d %d %d\n", &n, &m, &d); vector<int> nr_roads(n+1); vector<int> groups(n+1); vector< vector<int> > roads(n+1); for(int i=0; i<m; i++) { scanf("%d %d\n", &x, &y); nr_roads[x]++; roads[x].push_back(y); nr_roads[y]++; roads[y].push_back(x); } vector<int> to_delete; for(int i=1; i<=n; i++) { if(nr_roads[i] < d) { groups[i] = -1; to_delete.push_back(i); } } while(to_delete.size()) { x = to_delete.back(); to_delete.pop_back(); for(int i=0; i<roads[x].size(); i++) { nr_roads[roads[x].at(i)]--; if(nr_roads[roads[x].at(i)] == d-1) { groups[roads[x].at(i)] = -1; to_delete.push_back(roads[x].at(i)); } } } int best = 0, best_nr = 0, current = 0; vector<int> frontier; for(int i=1; i<=n; i++) { if(groups[i] == 0) { groups[i] = i; current++; frontier.push_back(i); } while(frontier.size()) { x = frontier.back(); frontier.pop_back(); for(int j=0; j<roads[x].size(); j++) { if(groups[roads[x].at(j)] == 0) { groups[roads[x].at(j)] = i; current++; frontier.push_back(roads[x].at(j)); } } } if(current > best) { best = current; best_nr = i; } current = 0; } if(!best) printf("NIE\n"); else { printf("%d\n", best); for(int i=1; i<=n; i++) { if(groups[i] == best_nr) printf("%d ", i); } printf("\n"); } return 0; } |