#include <cstdio> #include <cstdlib> #include <vector> #include <map> #include <algorithm> #include <set> #include <time.h> #include <queue> #include <list> using namespace std; typedef struct { list<int> adj; int adj_size; bool deleted, visited; } Vertex; int main () { int n, m, d, a, b; Vertex v; v.adj_size = 0; v.deleted = false; v.visited = false; scanf("%d %d %d", &n, &m, &d); vector<Vertex> V(n, v); for (int i = 0; i < m; ++i) { scanf("%d %d", &a, &b); --a; --b; V[a].adj.push_back(b); V[b].adj.push_back(a); } list<int> del_que; for (int i = 0; i < n; ++i) { V[i].adj_size = V[i].adj.size(); if (V[i].adj_size < d) { del_que.push_back(i); } } while (!del_que.empty()) { a = del_que.front(); del_que.pop_front(); V[a].deleted = true; V[a].adj_size = 0; for (list<int>::iterator it = V[a].adj.begin(); it != V[a].adj.end(); it++) { if (V[*it].deleted) { continue; } V[*it].adj_size--; if (V[*it].adj_size == d - 1) { del_que.push_back(*it); } } V[a].adj.clear(); } for (int i = 0; i < n; ++i) { list<int>::iterator it = V[i].adj.begin(); while (it != V[i].adj.end()) { if (V[*it].adj_size < d) { it = V[i].adj.erase(it); } else { it++; } } } list<int> bfs; vector<int> best; int max_size = 0; for (int i = 0; i < n; ++i) { if (V[i].deleted || V[i].visited) { continue; } int size = 1; V[i].visited = true; bfs.push_back(i); vector<int> cur; cur.push_back(i); while (!bfs.empty()) { int j = bfs.front(); bfs.pop_front(); for (list<int>::iterator it = V[j].adj.begin(); it != V[j].adj.end(); it++) { if (V[*it].visited) { continue; } V[*it].visited = true; bfs.push_back(*it); size++; cur.push_back(*it); } } if (size > max_size) { max_size = size; best = cur; } } if (max_size) { printf("%d\n", max_size); for (int i = 0; i < max_size - 1; ++i) { printf("%d ", best[i] + 1); } printf("%d\n", best[max_size - 1] + 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 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 103 104 105 106 107 108 109 | #include <cstdio> #include <cstdlib> #include <vector> #include <map> #include <algorithm> #include <set> #include <time.h> #include <queue> #include <list> using namespace std; typedef struct { list<int> adj; int adj_size; bool deleted, visited; } Vertex; int main () { int n, m, d, a, b; Vertex v; v.adj_size = 0; v.deleted = false; v.visited = false; scanf("%d %d %d", &n, &m, &d); vector<Vertex> V(n, v); for (int i = 0; i < m; ++i) { scanf("%d %d", &a, &b); --a; --b; V[a].adj.push_back(b); V[b].adj.push_back(a); } list<int> del_que; for (int i = 0; i < n; ++i) { V[i].adj_size = V[i].adj.size(); if (V[i].adj_size < d) { del_que.push_back(i); } } while (!del_que.empty()) { a = del_que.front(); del_que.pop_front(); V[a].deleted = true; V[a].adj_size = 0; for (list<int>::iterator it = V[a].adj.begin(); it != V[a].adj.end(); it++) { if (V[*it].deleted) { continue; } V[*it].adj_size--; if (V[*it].adj_size == d - 1) { del_que.push_back(*it); } } V[a].adj.clear(); } for (int i = 0; i < n; ++i) { list<int>::iterator it = V[i].adj.begin(); while (it != V[i].adj.end()) { if (V[*it].adj_size < d) { it = V[i].adj.erase(it); } else { it++; } } } list<int> bfs; vector<int> best; int max_size = 0; for (int i = 0; i < n; ++i) { if (V[i].deleted || V[i].visited) { continue; } int size = 1; V[i].visited = true; bfs.push_back(i); vector<int> cur; cur.push_back(i); while (!bfs.empty()) { int j = bfs.front(); bfs.pop_front(); for (list<int>::iterator it = V[j].adj.begin(); it != V[j].adj.end(); it++) { if (V[*it].visited) { continue; } V[*it].visited = true; bfs.push_back(*it); size++; cur.push_back(*it); } } if (size > max_size) { max_size = size; best = cur; } } if (max_size) { printf("%d\n", max_size); for (int i = 0; i < max_size - 1; ++i) { printf("%d ", best[i] + 1); } printf("%d\n", best[max_size - 1] + 1); } else { printf("NIE\n"); } return 0; } |