// Aleksander Kramarz #include <cstdio> #include <vector> using namespace std; int n, m, d, u, v, pos[200005], deg[200005], comp[200005]; vector<int> graph[200005], by_deg[200005]; bool del[200005]; int bfs(int s) { vector<int> q; q.push_back(s); comp[s] = v; for (int i = 0; i < q.size(); i++) { for (int j = 0; j < graph[q[i]].size(); j++) { u = graph[q[i]][j]; if (!del[u] && !comp[u]) { comp[u] = v; q.push_back(u); } } } return q.size(); } int main() { scanf("%d%d%d", &n, &m, &d); while (m--) { scanf("%d%d", &u, &v); graph[u].push_back(v); graph[v].push_back(u); } for (int i = 1; i <= n; i++) { deg[i] = graph[i].size(); pos[i] = by_deg[graph[i].size()].size(); by_deg[graph[i].size()].push_back(i); } for (int i = 0; i < d; i++) { for (int j = 0; j < by_deg[i].size(); j++) { del[by_deg[i][j]] = true; for (int k = 0; k < graph[by_deg[i][j]].size(); k++) { v = graph[by_deg[i][j]][k]; if (deg[v] > i && !del[v]) { if (v != by_deg[deg[v]].back()) { u = by_deg[deg[v]].back(); swap(by_deg[deg[v]][pos[v]], by_deg[deg[v]].back()); pos[u] = pos[v]; } by_deg[deg[v]].pop_back(); deg[v]--; pos[v] = by_deg[deg[v]].size(); by_deg[deg[v]].push_back(v); } } } } int res, res_size = 0; v = 0; for (int i = 1; i <= n; i++) { if (!del[i] && !comp[i]) { v++; int comp_size = bfs(i); if (comp_size > res_size) { res_size = comp_size; res = v; } } } if (res_size == 0) printf("NIE\n"); else { printf("%d\n", res_size); for (int i = 1; i <= n; i++) if (comp[i] == v) printf("%d ", i); printf("\n"); } }
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 | // Aleksander Kramarz #include <cstdio> #include <vector> using namespace std; int n, m, d, u, v, pos[200005], deg[200005], comp[200005]; vector<int> graph[200005], by_deg[200005]; bool del[200005]; int bfs(int s) { vector<int> q; q.push_back(s); comp[s] = v; for (int i = 0; i < q.size(); i++) { for (int j = 0; j < graph[q[i]].size(); j++) { u = graph[q[i]][j]; if (!del[u] && !comp[u]) { comp[u] = v; q.push_back(u); } } } return q.size(); } int main() { scanf("%d%d%d", &n, &m, &d); while (m--) { scanf("%d%d", &u, &v); graph[u].push_back(v); graph[v].push_back(u); } for (int i = 1; i <= n; i++) { deg[i] = graph[i].size(); pos[i] = by_deg[graph[i].size()].size(); by_deg[graph[i].size()].push_back(i); } for (int i = 0; i < d; i++) { for (int j = 0; j < by_deg[i].size(); j++) { del[by_deg[i][j]] = true; for (int k = 0; k < graph[by_deg[i][j]].size(); k++) { v = graph[by_deg[i][j]][k]; if (deg[v] > i && !del[v]) { if (v != by_deg[deg[v]].back()) { u = by_deg[deg[v]].back(); swap(by_deg[deg[v]][pos[v]], by_deg[deg[v]].back()); pos[u] = pos[v]; } by_deg[deg[v]].pop_back(); deg[v]--; pos[v] = by_deg[deg[v]].size(); by_deg[deg[v]].push_back(v); } } } } int res, res_size = 0; v = 0; for (int i = 1; i <= n; i++) { if (!del[i] && !comp[i]) { v++; int comp_size = bfs(i); if (comp_size > res_size) { res_size = comp_size; res = v; } } } if (res_size == 0) printf("NIE\n"); else { printf("%d\n", res_size); for (int i = 1; i <= n; i++) if (comp[i] == v) printf("%d ", i); printf("\n"); } } |