#include <cstdio> #include <vector> using namespace std; const int MAX_N = 200005; vector <int> G[MAX_N]; int grupa[MAX_N]; int deg[MAX_N]; int kol[MAX_N], pp, kk; int ile; void dfs(int v, int x) { ile++; grupa[v] = x; for (int i=0; i<(int)G[v].size(); i++) if (grupa[G[v][i]] == 0) dfs(G[v][i], x); } int main() { int n, m, d; scanf("%d%d%d", &n, &m, &d); for (int i=0; i<m; i++) { int a, b; scanf("%d%d", &a, &b); G[a].push_back(b); G[b].push_back(a); deg[a]++; deg[b]++; } for (int i=1; i<=n; i++) if ((int)G[i].size() < d) { kol[kk] = i; kk++; grupa[i] = -1; } while (pp != kk) { int v = kol[pp]; pp++; for (int i=0; i<(int)G[v].size(); i++) { deg[G[v][i]]--; if (deg[G[v][i]] == d-1) { kol[kk] = G[v][i]; kk++; grupa[G[v][i]] = -1; } } } int x = 0; int ile_maks = -1, x_maks = 0; for (int i=1; i<=n; i++) if (grupa[i] == 0) { ile = 0; x++; dfs(i, x); if (ile > ile_maks) { ile_maks = ile; x_maks = x; } } if (ile_maks < 0) { printf("NIE\n"); return 0; } printf("%d\n", ile_maks); for (int i=1; i<=n; i++) if (grupa[i] == x_maks) 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 | #include <cstdio> #include <vector> using namespace std; const int MAX_N = 200005; vector <int> G[MAX_N]; int grupa[MAX_N]; int deg[MAX_N]; int kol[MAX_N], pp, kk; int ile; void dfs(int v, int x) { ile++; grupa[v] = x; for (int i=0; i<(int)G[v].size(); i++) if (grupa[G[v][i]] == 0) dfs(G[v][i], x); } int main() { int n, m, d; scanf("%d%d%d", &n, &m, &d); for (int i=0; i<m; i++) { int a, b; scanf("%d%d", &a, &b); G[a].push_back(b); G[b].push_back(a); deg[a]++; deg[b]++; } for (int i=1; i<=n; i++) if ((int)G[i].size() < d) { kol[kk] = i; kk++; grupa[i] = -1; } while (pp != kk) { int v = kol[pp]; pp++; for (int i=0; i<(int)G[v].size(); i++) { deg[G[v][i]]--; if (deg[G[v][i]] == d-1) { kol[kk] = G[v][i]; kk++; grupa[G[v][i]] = -1; } } } int x = 0; int ile_maks = -1, x_maks = 0; for (int i=1; i<=n; i++) if (grupa[i] == 0) { ile = 0; x++; dfs(i, x); if (ile > ile_maks) { ile_maks = ile; x_maks = x; } } if (ile_maks < 0) { printf("NIE\n"); return 0; } printf("%d\n", ile_maks); for (int i=1; i<=n; i++) if (grupa[i] == x_maks) printf("%d ", i); printf("\n"); } |