#include <cstdio> #include <cstdlib> #include <vector> #include <queue> #include <algorithm> using namespace std; const int N_MAX = 200000; vector<int> G[N_MAX]; int degree[N_MAX]; int connected[N_MAX]; int connected_size[N_MAX]; int maks_connected_size = 0; int maks_connected_id = -1; int n, m, d; void dfs(int v, int id) { connected[v] = id; connected_size[id]++; for (int i = 0; i < G[v].size(); ++i) { int u = G[v][i]; if (degree[u] >= d && connected[u] == -1) { dfs(u, id); } } } void print_array(int *arr, int size) { for (int i = 0; i < size; ++i) { printf("%d ", arr[i]); } printf("\n"); } void print_vector(vector<int> v) { for (int i = 0; i < v.size(); ++i) { printf("%d ", v[i] + 1); } printf("\n"); } int main() { scanf("%d %d %d", &n, &m, &d); for (int i = 0; i < m; ++i) { int a, b; scanf("%d %d", &a, &b); --a, --b; G[a].push_back(b); G[b].push_back(a); ++degree[a]; ++degree[b]; } queue<int> q; for (int i = 0; i < n; ++i) { if (degree[i] < d) { q.push(i); degree[i] = 0; } connected[i] = -1; connected_size[i] = 0; } while (!q.empty()) { int v = q.front(); q.pop(); for (int i = 0; i < G[v].size(); ++i) { int u = G[v][i]; if (degree[u] == d) { q.push(u); degree[u] = 0; } else if (degree[u] != 0) { degree[u]--; } } } for (int i = 0; i < n; ++i) { if (degree[i] >= d && connected[i] == -1) { dfs(i, i); if (maks_connected_size < connected_size[i]) { maks_connected_size = connected_size[i]; maks_connected_id = i; } } } if (maks_connected_size == 0) { printf("NIE\n"); } else { printf("%d\n", maks_connected_size); int count = 0; for (int i = 0; i < n; ++i) { if (connected[i] == maks_connected_id) { printf("%d", i+1); ++count; if (i != maks_connected_size) printf(" "); } } 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 | #include <cstdio> #include <cstdlib> #include <vector> #include <queue> #include <algorithm> using namespace std; const int N_MAX = 200000; vector<int> G[N_MAX]; int degree[N_MAX]; int connected[N_MAX]; int connected_size[N_MAX]; int maks_connected_size = 0; int maks_connected_id = -1; int n, m, d; void dfs(int v, int id) { connected[v] = id; connected_size[id]++; for (int i = 0; i < G[v].size(); ++i) { int u = G[v][i]; if (degree[u] >= d && connected[u] == -1) { dfs(u, id); } } } void print_array(int *arr, int size) { for (int i = 0; i < size; ++i) { printf("%d ", arr[i]); } printf("\n"); } void print_vector(vector<int> v) { for (int i = 0; i < v.size(); ++i) { printf("%d ", v[i] + 1); } printf("\n"); } int main() { scanf("%d %d %d", &n, &m, &d); for (int i = 0; i < m; ++i) { int a, b; scanf("%d %d", &a, &b); --a, --b; G[a].push_back(b); G[b].push_back(a); ++degree[a]; ++degree[b]; } queue<int> q; for (int i = 0; i < n; ++i) { if (degree[i] < d) { q.push(i); degree[i] = 0; } connected[i] = -1; connected_size[i] = 0; } while (!q.empty()) { int v = q.front(); q.pop(); for (int i = 0; i < G[v].size(); ++i) { int u = G[v][i]; if (degree[u] == d) { q.push(u); degree[u] = 0; } else if (degree[u] != 0) { degree[u]--; } } } for (int i = 0; i < n; ++i) { if (degree[i] >= d && connected[i] == -1) { dfs(i, i); if (maks_connected_size < connected_size[i]) { maks_connected_size = connected_size[i]; maks_connected_id = i; } } } if (maks_connected_size == 0) { printf("NIE\n"); } else { printf("%d\n", maks_connected_size); int count = 0; for (int i = 0; i < n; ++i) { if (connected[i] == maks_connected_id) { printf("%d", i+1); ++count; if (i != maks_connected_size) printf(" "); } } printf("\n"); } return 0; } |