#include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; int n, m, d, x, y, liczba_sasiadow[200005], niedobry_wierzch, pocz_kolejki_dfs, maxi = 0, indeks; vector <int> lista_sasiedztwa[200005], vector_z_wynikami[200005]; bool czy_jest_w_kolejce[200005], czy_juz_byl_w_dfs[200005]; queue <int> kolejka_niedobrych, kolejka_dfs; int main() { scanf ("%d %d %d", &n, &m, &d); for (int i=0; i<m; i++) { scanf ("%d %d", &x, &y); lista_sasiedztwa[x].push_back(y); lista_sasiedztwa[y].push_back(x); liczba_sasiadow[x]++; liczba_sasiadow[y]++; } for (int i=1; i<=n; i++) { if(liczba_sasiadow[i] < d) { kolejka_niedobrych.push(i); czy_jest_w_kolejce[i] = true; } } while(!kolejka_niedobrych.empty()) { niedobry_wierzch = kolejka_niedobrych.front(); kolejka_niedobrych.pop(); for (int i=0; i<lista_sasiedztwa[niedobry_wierzch].size(); i++) { liczba_sasiadow[lista_sasiedztwa[niedobry_wierzch][i]]--; if(liczba_sasiadow[lista_sasiedztwa[niedobry_wierzch][i]] < d && czy_jest_w_kolejce[lista_sasiedztwa[niedobry_wierzch][i]] == false) { czy_jest_w_kolejce[lista_sasiedztwa[niedobry_wierzch][i]] = true; kolejka_niedobrych.push(lista_sasiedztwa[niedobry_wierzch][i]); } } } for (int i=1; i<=n; i++) { if(liczba_sasiadow[i] >= d && czy_juz_byl_w_dfs[i] == false) { czy_juz_byl_w_dfs[i] = true; kolejka_dfs.push(i); while(!kolejka_dfs.empty()) { pocz_kolejki_dfs = kolejka_dfs.front(); vector_z_wynikami[i].push_back(pocz_kolejki_dfs); kolejka_dfs.pop(); for (int j=0; j<lista_sasiedztwa[pocz_kolejki_dfs].size(); j++) { if(liczba_sasiadow[lista_sasiedztwa[pocz_kolejki_dfs][j]] >= d && czy_juz_byl_w_dfs[lista_sasiedztwa[pocz_kolejki_dfs][j]] == false) { czy_juz_byl_w_dfs[lista_sasiedztwa[pocz_kolejki_dfs][j]] = true; kolejka_dfs.push(lista_sasiedztwa[pocz_kolejki_dfs][j]); } } } if(vector_z_wynikami[i].size() > maxi) { maxi = vector_z_wynikami[i].size(); indeks = i; } } } if(maxi == 0) printf ("NIE\n"); else { printf ("%d\n", maxi); sort(vector_z_wynikami[indeks].begin(), vector_z_wynikami[indeks].end()); for (int i=0; i<vector_z_wynikami[indeks].size(); i++) { printf ("%d ", vector_z_wynikami[indeks][i]); } } }
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 | #include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; int n, m, d, x, y, liczba_sasiadow[200005], niedobry_wierzch, pocz_kolejki_dfs, maxi = 0, indeks; vector <int> lista_sasiedztwa[200005], vector_z_wynikami[200005]; bool czy_jest_w_kolejce[200005], czy_juz_byl_w_dfs[200005]; queue <int> kolejka_niedobrych, kolejka_dfs; int main() { scanf ("%d %d %d", &n, &m, &d); for (int i=0; i<m; i++) { scanf ("%d %d", &x, &y); lista_sasiedztwa[x].push_back(y); lista_sasiedztwa[y].push_back(x); liczba_sasiadow[x]++; liczba_sasiadow[y]++; } for (int i=1; i<=n; i++) { if(liczba_sasiadow[i] < d) { kolejka_niedobrych.push(i); czy_jest_w_kolejce[i] = true; } } while(!kolejka_niedobrych.empty()) { niedobry_wierzch = kolejka_niedobrych.front(); kolejka_niedobrych.pop(); for (int i=0; i<lista_sasiedztwa[niedobry_wierzch].size(); i++) { liczba_sasiadow[lista_sasiedztwa[niedobry_wierzch][i]]--; if(liczba_sasiadow[lista_sasiedztwa[niedobry_wierzch][i]] < d && czy_jest_w_kolejce[lista_sasiedztwa[niedobry_wierzch][i]] == false) { czy_jest_w_kolejce[lista_sasiedztwa[niedobry_wierzch][i]] = true; kolejka_niedobrych.push(lista_sasiedztwa[niedobry_wierzch][i]); } } } for (int i=1; i<=n; i++) { if(liczba_sasiadow[i] >= d && czy_juz_byl_w_dfs[i] == false) { czy_juz_byl_w_dfs[i] = true; kolejka_dfs.push(i); while(!kolejka_dfs.empty()) { pocz_kolejki_dfs = kolejka_dfs.front(); vector_z_wynikami[i].push_back(pocz_kolejki_dfs); kolejka_dfs.pop(); for (int j=0; j<lista_sasiedztwa[pocz_kolejki_dfs].size(); j++) { if(liczba_sasiadow[lista_sasiedztwa[pocz_kolejki_dfs][j]] >= d && czy_juz_byl_w_dfs[lista_sasiedztwa[pocz_kolejki_dfs][j]] == false) { czy_juz_byl_w_dfs[lista_sasiedztwa[pocz_kolejki_dfs][j]] = true; kolejka_dfs.push(lista_sasiedztwa[pocz_kolejki_dfs][j]); } } } if(vector_z_wynikami[i].size() > maxi) { maxi = vector_z_wynikami[i].size(); indeks = i; } } } if(maxi == 0) printf ("NIE\n"); else { printf ("%d\n", maxi); sort(vector_z_wynikami[indeks].begin(), vector_z_wynikami[indeks].end()); for (int i=0; i<vector_z_wynikami[indeks].size(); i++) { printf ("%d ", vector_z_wynikami[indeks][i]); } } } |