#include <algorithm> #include <cstdio> #include <queue> #include <vector> using namespace std; const int r = 200005; vector<int> g[r]; vector <int> wynik; bool czy_istnieje[r], odw[r], odw2[r]; int liczba_sasiadow[r]; int ilosc = 1; void dfs(int w){ if(odw[w] == 0 && czy_istnieje[w] == 0){ odw[w] = 1; for(int i = 0; i < g[w].size(); i++){ if(odw[g[w][i]] == 0 && czy_istnieje[g[w][i]] == 0){ ilosc++; dfs(g[w][i]); } } } } void wrzuc(int w){ if(odw2[w] == 0 && czy_istnieje[w] == 0){ odw2[w] = 1; for(int i = 0; i < g[w].size(); i++){ if(odw2[g[w][i]] == 0 && czy_istnieje[g[w][i]] == 0){ wynik.push_back(g[w][i]); wrzuc(g[w][i]); } } } } int main(){ int n, m, d; scanf("%d%d%d", &n, &m, &d); int a, b; for(int i = 0; i<m; i++){ scanf("%d%d", &a, &b); g[a].push_back(b); g[b].push_back(a); liczba_sasiadow[a]++; liczba_sasiadow[b]++; } /* for(int i = 1; i<=n; i++){ printf("\n%d:\n", i); for(int j = 0; j<g[i].size(); j++) printf("%d ", g[i][j]); }*/ queue <int> usun; for(int i = 1; i <= n; i++){ if(liczba_sasiadow[i] < d) { usun.push(i); czy_istnieje[i] = 1; } } while(!usun.empty()){ for(int i = 0; i < g[usun.front()].size(); i++){ liczba_sasiadow[g[usun.front()][i]]--; if(liczba_sasiadow[g[usun.front()][i]] < d && czy_istnieje[g[usun.front()][i]] == 0) { usun.push(g[usun.front()][i]); czy_istnieje[g[usun.front()][i]] = 1; } } usun.pop(); } // for(int i = 1; i<=n; i++) if(czy_istnieje[i] == 0) printf("%d\n", i); int max = 0, p = 0; for(int i = 1; i <= n; i++) { ilosc = 1; if(odw[i] == 0 && czy_istnieje[i] == 0) dfs(i); if(ilosc > max){ max = ilosc; p = i; } } if(max == 1 || max == 0){ printf("NIE\n"); return 0; } wynik.push_back(p); wrzuc(p); sort(wynik.begin(), wynik.end()); printf("%d\n", max); for(int i = 0; i<wynik.size(); i++) printf("%d ", wynik[i]); 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 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 | #include <algorithm> #include <cstdio> #include <queue> #include <vector> using namespace std; const int r = 200005; vector<int> g[r]; vector <int> wynik; bool czy_istnieje[r], odw[r], odw2[r]; int liczba_sasiadow[r]; int ilosc = 1; void dfs(int w){ if(odw[w] == 0 && czy_istnieje[w] == 0){ odw[w] = 1; for(int i = 0; i < g[w].size(); i++){ if(odw[g[w][i]] == 0 && czy_istnieje[g[w][i]] == 0){ ilosc++; dfs(g[w][i]); } } } } void wrzuc(int w){ if(odw2[w] == 0 && czy_istnieje[w] == 0){ odw2[w] = 1; for(int i = 0; i < g[w].size(); i++){ if(odw2[g[w][i]] == 0 && czy_istnieje[g[w][i]] == 0){ wynik.push_back(g[w][i]); wrzuc(g[w][i]); } } } } int main(){ int n, m, d; scanf("%d%d%d", &n, &m, &d); int a, b; for(int i = 0; i<m; i++){ scanf("%d%d", &a, &b); g[a].push_back(b); g[b].push_back(a); liczba_sasiadow[a]++; liczba_sasiadow[b]++; } /* for(int i = 1; i<=n; i++){ printf("\n%d:\n", i); for(int j = 0; j<g[i].size(); j++) printf("%d ", g[i][j]); }*/ queue <int> usun; for(int i = 1; i <= n; i++){ if(liczba_sasiadow[i] < d) { usun.push(i); czy_istnieje[i] = 1; } } while(!usun.empty()){ for(int i = 0; i < g[usun.front()].size(); i++){ liczba_sasiadow[g[usun.front()][i]]--; if(liczba_sasiadow[g[usun.front()][i]] < d && czy_istnieje[g[usun.front()][i]] == 0) { usun.push(g[usun.front()][i]); czy_istnieje[g[usun.front()][i]] = 1; } } usun.pop(); } // for(int i = 1; i<=n; i++) if(czy_istnieje[i] == 0) printf("%d\n", i); int max = 0, p = 0; for(int i = 1; i <= n; i++) { ilosc = 1; if(odw[i] == 0 && czy_istnieje[i] == 0) dfs(i); if(ilosc > max){ max = ilosc; p = i; } } if(max == 1 || max == 0){ printf("NIE\n"); return 0; } wynik.push_back(p); wrzuc(p); sort(wynik.begin(), wynik.end()); printf("%d\n", max); for(int i = 0; i<wynik.size(); i++) printf("%d ", wynik[i]); return 0; } |