3567 | 2023. 03. 01 08:10:44 | gitty | Hálózati biztonság (50) | cpp17 | Futási hiba 22/50 | 32ms | 64176 KiB |
#include <bits/stdc++.h>
using namespace std;
bool **g;
int main()
{
//ifstream cin("in.txt");
int n, m, k;
int torol=1;
cin >> n >> m >> k;
vector<int> szamlalo(n + 1, 0);
vector<int> elod(n + 1, 0);
g = new bool*[n + 1];
for(int i = 1; i <= n; i++){
g[i] = new bool[n + 1];
}
for(int i = 1; i <= n; i++){
for(int j = 0; j <= n; j++){
g[i][j] = 0;
}
}
for(int i = 1; i <= m; i++){
int x, y;
cin >> x >> y;
g[x][y] = 1;
g[y][x] = 1;
szamlalo[x]++;
szamlalo[y]++;
}
// for(int i = 1; i <= n; i++){
//
// cout << i << ": ";
// for(int j = 1; j <= n; j++){
// cout << g[i][j] << " ";
// }
//
// cout << "\n";
// }
//
// cout << "\n";
while(torol==1)
{
torol = 0;
for(int i = 1; i <= n; i++){
if(szamlalo[i] < k && szamlalo[i] > 0){
torol=1;
for(int j = 1; j <= n; j++){
if(g[i][j]!=0){
szamlalo[i]--;
g[i][j] = 0;
}
}
for(int j = 1; j <= n; j++){
if(g[j][i]!=0){
szamlalo[j]--;
g[j][i] = 0;
}
}
}
}
}
// for(int i = 1; i <= n; i++){
//
// cout << i << ": ";
// for(int j = 1; j <= n; j++){
// cout << g[i][j] << " ";
// }
//
// cout << "\n";
// }
vector<int> os(n + 1, -1);
for(int i = 1; i <= n; i++){
if(szamlalo[i] >= k){
for(int j = i+1; j <= n; j++){
if(g[i][j]!=0){
if(os[i] == -1){
os[i] = i;
elod[os[i]]++;
}
if(os[j]==-1)
elod[os[i]]++;
os[j] = os[i];
}
}
}
}
int ma = 0;
int ind = 0;
for(int i = 1; i <= n; i++){
if(elod[i] >= ma){
ma = elod[i];
ind = i;
}
}
int db = 0;
for(int i = 1; i <= n; i++){
if(os[i] == ind){
db++;
}
}
cout << db << "\n";
for(int i = 1; i <= n; i++){
if(os[i] == ind){
cout << i << " ";
}
}
/// rezgraf szamolas es hasonlitas
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 22/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1812 KiB | |||
2 | Futási hiba | 0/0 | 28ms | 64176 KiB | |||
3 | Elfogadva | 2/2 | 3ms | 2228 KiB | |||
4 | Elfogadva | 2/2 | 3ms | 2456 KiB | |||
5 | Hibás válasz | 0/2 | 3ms | 2816 KiB | |||
6 | Elfogadva | 2/2 | 3ms | 2896 KiB | |||
7 | Elfogadva | 2/2 | 3ms | 3292 KiB | |||
8 | Elfogadva | 2/2 | 3ms | 3284 KiB | |||
9 | Elfogadva | 2/2 | 3ms | 3728 KiB | |||
10 | Hibás válasz | 0/2 | 8ms | 5688 KiB | |||
11 | Elfogadva | 2/2 | 8ms | 11832 KiB | |||
12 | Elfogadva | 2/2 | 29ms | 21600 KiB | |||
13 | Elfogadva | 3/3 | 20ms | 21564 KiB | |||
14 | Futási hiba | 0/3 | 32ms | 62960 KiB | |||
15 | Futási hiba | 0/3 | 32ms | 62788 KiB | |||
16 | Futási hiba | 0/3 | 32ms | 62640 KiB | |||
17 | Futási hiba | 0/3 | 26ms | 62800 KiB | |||
18 | Futási hiba | 0/3 | 32ms | 62196 KiB | |||
19 | Futási hiba | 0/3 | 28ms | 61544 KiB | |||
20 | Futási hiba | 0/3 | 32ms | 61324 KiB | |||
21 | Futási hiba | 0/3 | 24ms | 61292 KiB | |||
22 | Elfogadva | 3/3 | 3ms | 4420 KiB |