#include <stdio.h> #include <set> #include <vector> #define MAX 200010 using namespace std; set<int> neighbours[MAX]; vector<int> todo; int done[MAX]; int dfs_done[MAX]; int n, m, d; void dfs(int node, vector<int> *vis) { vis->push_back(node); dfs_done[node] = 1; for (set<int>::iterator it = neighbours[node].begin(); it != neighbours[node].end(); ++it) { if (!dfs_done[*it]) dfs(*it, vis); } } int main() { int x, y; scanf("%d %d %d", &n, &m, &d); for (int i = 0; i < m; ++i) { scanf("%d %d", &x, &y); neighbours[x].insert(y); neighbours[y].insert(x); } for (int i = 1; i <= n; ++i) { if (neighbours[i].size() < d) { todo.push_back(i); done[i] = 1; } } int index = 0; //Remove all nodes with neighbours size larger than d while (index != todo.size()) { int id = todo[index]; for (set<int>::iterator it = neighbours[id].begin(); it != neighbours[id].end(); ++it) { neighbours[*it].erase(id); if (!done[*it] && neighbours[*it].size() < d) { todo.push_back(*it); done[*it] = 1; } } ++index; } vector<int> best; //Now check connectivity graph for (int i = 1; i <= n; ++i) { if (!dfs_done[i] && !done[i]) { vector<int> vect; dfs(i, &vect); if (best.size() < vect.size()) best = vect; } } if (best.size() == 0) printf("NIE\n"); else { printf("%d\n", best.size()); printf("%d", best[0]); for (int i = 1; i < best.size(); ++i) printf(" %d", best[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 <stdio.h> #include <set> #include <vector> #define MAX 200010 using namespace std; set<int> neighbours[MAX]; vector<int> todo; int done[MAX]; int dfs_done[MAX]; int n, m, d; void dfs(int node, vector<int> *vis) { vis->push_back(node); dfs_done[node] = 1; for (set<int>::iterator it = neighbours[node].begin(); it != neighbours[node].end(); ++it) { if (!dfs_done[*it]) dfs(*it, vis); } } int main() { int x, y; scanf("%d %d %d", &n, &m, &d); for (int i = 0; i < m; ++i) { scanf("%d %d", &x, &y); neighbours[x].insert(y); neighbours[y].insert(x); } for (int i = 1; i <= n; ++i) { if (neighbours[i].size() < d) { todo.push_back(i); done[i] = 1; } } int index = 0; //Remove all nodes with neighbours size larger than d while (index != todo.size()) { int id = todo[index]; for (set<int>::iterator it = neighbours[id].begin(); it != neighbours[id].end(); ++it) { neighbours[*it].erase(id); if (!done[*it] && neighbours[*it].size() < d) { todo.push_back(*it); done[*it] = 1; } } ++index; } vector<int> best; //Now check connectivity graph for (int i = 1; i <= n; ++i) { if (!dfs_done[i] && !done[i]) { vector<int> vect; dfs(i, &vect); if (best.size() < vect.size()) best = vect; } } if (best.size() == 0) printf("NIE\n"); else { printf("%d\n", best.size()); printf("%d", best[0]); for (int i = 1; i < best.size(); ++i) printf(" %d", best[i]); printf("\n"); } return 0; } |