#include<cstdio> #include<iostream> #include<algorithm> #include<vector> #define ST first #define ND second #define MP make_pair #define PB push_back #define PF push_front #define PBX pop_back #define PFX pop_front #define MIN(a,b) (a<b)?(a):(b) #define MAX(a,b) (a>b)?(a):(b) using namespace std; const int MAXN = 2e5; const int MAXM = 2e5; int n, m, d; vector<int> Graf[MAXN+10]; vector<int> Odpowiedz; bool Nalezace[MAXN+10]; bool Zbiory[MAXN+10]; void Usun(int w) { int Il=0; int i=0; while(i < Graf[w].size()) { if(Nalezace[Graf[w][i]] == false) { swap(Graf[w][i], Graf[w].back()); Graf[w].PBX(); i--; } else Il++; i++; } if(Il < d) { Nalezace[w] = false; for(i=0; i<Graf[w].size(); i++) { if(Nalezace[Graf[w][i]] == true) Usun(Graf[w][i]); } } } int Odw[MAXN+10]; int duba=1; int DFS(int w) { Zbiory[w] = true; Odw[w] = duba; int Res=0; for(int i=0; i<Graf[w].size(); i++) { if(Odw[Graf[w][i]] < duba) { Res += DFS(Graf[w][i]); } } return Res+1; } void Zloz(int w) { Odw[w] = duba; Odpowiedz.PB(w); for(int i=0; i<Graf[w].size(); i++) { if(Odw[Graf[w][i]] < duba) { Zloz(Graf[w][i]); } } } int main() { scanf("%d%d%d", &n, &m, &d); for(int i=1; i<=n; i++) { Nalezace[i] = true; } for(int i=0; i<m; i++) { int a, b; scanf("%d%d", &a, &b); Graf[a].PB(b); Graf[b].PB(a); } for(int i=1; i<=n; i++) { Usun(i); } int Ilosc=0; int Ktory=0; for(int i=1; i<=n; i++) { if(!Zbiory[i] && Nalezace[i]) { int akt = DFS(i); duba++; if(akt > Ilosc) { Ktory = i; Ilosc = akt; } } } if(Ilosc == 0) { printf("NIE\n"); } else { printf("%d\n", Ilosc); duba++; Zloz(Ktory); sort(Odpowiedz.begin(), Odpowiedz.end()); for(int i=0; i<Odpowiedz.size(); i++) { printf("%d ", Odpowiedz[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 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 | #include<cstdio> #include<iostream> #include<algorithm> #include<vector> #define ST first #define ND second #define MP make_pair #define PB push_back #define PF push_front #define PBX pop_back #define PFX pop_front #define MIN(a,b) (a<b)?(a):(b) #define MAX(a,b) (a>b)?(a):(b) using namespace std; const int MAXN = 2e5; const int MAXM = 2e5; int n, m, d; vector<int> Graf[MAXN+10]; vector<int> Odpowiedz; bool Nalezace[MAXN+10]; bool Zbiory[MAXN+10]; void Usun(int w) { int Il=0; int i=0; while(i < Graf[w].size()) { if(Nalezace[Graf[w][i]] == false) { swap(Graf[w][i], Graf[w].back()); Graf[w].PBX(); i--; } else Il++; i++; } if(Il < d) { Nalezace[w] = false; for(i=0; i<Graf[w].size(); i++) { if(Nalezace[Graf[w][i]] == true) Usun(Graf[w][i]); } } } int Odw[MAXN+10]; int duba=1; int DFS(int w) { Zbiory[w] = true; Odw[w] = duba; int Res=0; for(int i=0; i<Graf[w].size(); i++) { if(Odw[Graf[w][i]] < duba) { Res += DFS(Graf[w][i]); } } return Res+1; } void Zloz(int w) { Odw[w] = duba; Odpowiedz.PB(w); for(int i=0; i<Graf[w].size(); i++) { if(Odw[Graf[w][i]] < duba) { Zloz(Graf[w][i]); } } } int main() { scanf("%d%d%d", &n, &m, &d); for(int i=1; i<=n; i++) { Nalezace[i] = true; } for(int i=0; i<m; i++) { int a, b; scanf("%d%d", &a, &b); Graf[a].PB(b); Graf[b].PB(a); } for(int i=1; i<=n; i++) { Usun(i); } int Ilosc=0; int Ktory=0; for(int i=1; i<=n; i++) { if(!Zbiory[i] && Nalezace[i]) { int akt = DFS(i); duba++; if(akt > Ilosc) { Ktory = i; Ilosc = akt; } } } if(Ilosc == 0) { printf("NIE\n"); } else { printf("%d\n", Ilosc); duba++; Zloz(Ktory); sort(Odpowiedz.begin(), Odpowiedz.end()); for(int i=0; i<Odpowiedz.size(); i++) { printf("%d ", Odpowiedz[i]); } } return 0; } |