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; } |
English