Niestety, nie byliśmy w stanie w pełni poprawnie wyświetlić tego pliku, ponieważ nie jest zakodowany w UTF-8.
Możesz pobrać ten plik i spróbować otworzyć go samodzielnie.
#include<iostream> #include<cstdio> #include<vector> #include<queue> #include<algorithm> using namespace std; const int MAX = 200001; int n, m, d, l[MAX]; vector<int> sasiedzi[MAX]; vector<int> klika[MAX]; queue<int> kol; bool sens[MAX]; int main() { scanf("%d%d%d", &n, &m, &d); int a, b; for (int i = 1; i <= m; i++) { scanf("%d%d", &a, &b); sasiedzi[a].push_back(b); sasiedzi[b].push_back(a); } for (int i = 1; i <= n; i++) { l[i] = sasiedzi[i].size(); if (sasiedzi[i].size() >= d) sens[i] = true; else { sens[i] = false; kol.push(i); } } while(!kol.empty()) { int w = kol.front(); kol.pop(); for (int i = 0; i < sasiedzi[w].size(); i++) { int k; k = sasiedzi[w][i]; l[k]--; if (l[k] < d && sens[k]) { sens[k] = 0; kol.push(k); } } } //Ten fragment odpowiada za tworzenie si� klik! int pocz = 1, nr = 0; while (pocz != n) { while(kol.empty()) { if (!sens[pocz]) pocz++; if (pocz > n) break; if (sens[pocz]) { kol.push(pocz); sens[pocz] = false; } } if (pocz > n) break; int w = kol.front(); kol.pop(); klika[nr].push_back(w); for(int i = 0; i < sasiedzi[w].size(); i++) { if (sens[sasiedzi[w][i]]) { kol.push(sasiedzi[w][i]); sens[sasiedzi[w][i]] = false; //cout << w << " " << sasiedzi[w][i] << " " << sasiedzi[sasiedzi[w][i]].size() << endl; } } if (kol.empty()) nr++; } int max = 0, dla = -1; if (nr == 0) {printf("NIE"); return 0;} else for (int i = 0; i < nr; i++) { if (klika[i].size() > max) { max = klika[i].size(); dla = i; } } if (max > 1) { sort (klika[dla].begin(), klika[dla].end()); printf("%d", max); printf("\n"); for (int i = 0; i < max; i++) { printf("%d ", klika[dla][i]); } } else {printf("NIE"); return 0;} 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 | #include<iostream> #include<cstdio> #include<vector> #include<queue> #include<algorithm> using namespace std; const int MAX = 200001; int n, m, d, l[MAX]; vector<int> sasiedzi[MAX]; vector<int> klika[MAX]; queue<int> kol; bool sens[MAX]; int main() { scanf("%d%d%d", &n, &m, &d); int a, b; for (int i = 1; i <= m; i++) { scanf("%d%d", &a, &b); sasiedzi[a].push_back(b); sasiedzi[b].push_back(a); } for (int i = 1; i <= n; i++) { l[i] = sasiedzi[i].size(); if (sasiedzi[i].size() >= d) sens[i] = true; else { sens[i] = false; kol.push(i); } } while(!kol.empty()) { int w = kol.front(); kol.pop(); for (int i = 0; i < sasiedzi[w].size(); i++) { int k; k = sasiedzi[w][i]; l[k]--; if (l[k] < d && sens[k]) { sens[k] = 0; kol.push(k); } } } //Ten fragment odpowiada za tworzenie si� klik! int pocz = 1, nr = 0; while (pocz != n) { while(kol.empty()) { if (!sens[pocz]) pocz++; if (pocz > n) break; if (sens[pocz]) { kol.push(pocz); sens[pocz] = false; } } if (pocz > n) break; int w = kol.front(); kol.pop(); klika[nr].push_back(w); for(int i = 0; i < sasiedzi[w].size(); i++) { if (sens[sasiedzi[w][i]]) { kol.push(sasiedzi[w][i]); sens[sasiedzi[w][i]] = false; //cout << w << " " << sasiedzi[w][i] << " " << sasiedzi[sasiedzi[w][i]].size() << endl; } } if (kol.empty()) nr++; } int max = 0, dla = -1; if (nr == 0) {printf("NIE"); return 0;} else for (int i = 0; i < nr; i++) { if (klika[i].size() > max) { max = klika[i].size(); dla = i; } } if (max > 1) { sort (klika[dla].begin(), klika[dla].end()); printf("%d", max); printf("\n"); for (int i = 0; i < max; i++) { printf("%d ", klika[dla][i]); } } else {printf("NIE"); return 0;} return 0; } |