#include<cstdio> #include<queue> #include<vector> #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define REP(i, n) FOR(i, 0, n) #define VERTICES 200000 using namespace std; vector<int> graph[VERTICES]; int deg[VERTICES]; bool pushed[VERTICES]; bool color[VERTICES]; int id[VERTICES]; queue<int> Q; int DFS(int v, int const& d, int const& ass_id) { int size = 1; color[v] = false; id[v] = ass_id; for (int neighbour : graph[v]) { if (color[neighbour] && (deg[neighbour] >= d)) { size += DFS(neighbour, d, ass_id); } } return size; } int main() { int n, m, d, a, b; scanf("%d%d%d", &n, &m, &d); while (m--) { scanf("%d%d", &a, &b); --a; --b; graph[a].push_back(b); graph[b].push_back(a); } for (int i = 0; i < n; ++i) { deg[i] = graph[i].size(); pushed[i] = false; if (deg[i] < d) { Q.push(i); pushed[i] = true; } } while (!Q.empty()) { int element = Q.front(); Q.pop(); for (int neighbour : graph[element]) { deg[neighbour]--; if ((deg[neighbour] < d) && !pushed[neighbour]) { Q.push(neighbour); pushed[neighbour] = true; } } } REP(i, n) { color[i] = true; id[i] = -1; } int id_cnt = 0; int max_size = 0, iid = -1; REP(i, n) { if (color[i] && (deg[i] >= d)) { int size = DFS(i, d, id_cnt); if (size > max_size) { max_size = size; iid = id_cnt; } id_cnt++; } } if (iid == -1) { printf("NIE\n"); } else { printf("%d\n", max_size); REP(i, n) { if (id[i] == iid) { printf("%d ", i + 1); } } 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 | #include<cstdio> #include<queue> #include<vector> #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define REP(i, n) FOR(i, 0, n) #define VERTICES 200000 using namespace std; vector<int> graph[VERTICES]; int deg[VERTICES]; bool pushed[VERTICES]; bool color[VERTICES]; int id[VERTICES]; queue<int> Q; int DFS(int v, int const& d, int const& ass_id) { int size = 1; color[v] = false; id[v] = ass_id; for (int neighbour : graph[v]) { if (color[neighbour] && (deg[neighbour] >= d)) { size += DFS(neighbour, d, ass_id); } } return size; } int main() { int n, m, d, a, b; scanf("%d%d%d", &n, &m, &d); while (m--) { scanf("%d%d", &a, &b); --a; --b; graph[a].push_back(b); graph[b].push_back(a); } for (int i = 0; i < n; ++i) { deg[i] = graph[i].size(); pushed[i] = false; if (deg[i] < d) { Q.push(i); pushed[i] = true; } } while (!Q.empty()) { int element = Q.front(); Q.pop(); for (int neighbour : graph[element]) { deg[neighbour]--; if ((deg[neighbour] < d) && !pushed[neighbour]) { Q.push(neighbour); pushed[neighbour] = true; } } } REP(i, n) { color[i] = true; id[i] = -1; } int id_cnt = 0; int max_size = 0, iid = -1; REP(i, n) { if (color[i] && (deg[i] >= d)) { int size = DFS(i, d, id_cnt); if (size > max_size) { max_size = size; iid = id_cnt; } id_cnt++; } } if (iid == -1) { printf("NIE\n"); } else { printf("%d\n", max_size); REP(i, n) { if (id[i] == iid) { printf("%d ", i + 1); } } printf("\n"); } return 0; } |