#include<iostream> #include<cstdio> #include<vector> using namespace std; int n, m, d; vector<int> tab[200001]; int tab2[200001]; int ss[200001]; int count[200001][2]; main() { scanf("%d %d %d", &n, &m, &d); for(int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); tab[a].push_back(b); tab[b].push_back(a); tab2[a]++; tab2[b]++; } bool enough = false; while(!enough) { enough = true; for(int i = 1; i <= n; i++) { if(tab2[i] != 0 && tab2[i] < d) { tab2[i] = 0; for(int k = 0; k < tab[i].size(); k++) { if(tab2[tab[i][k]]) { tab2[tab[i][k]]--; } } enough = false; } } } int counter = 1; for(int i = 1; i <= n; i++) { if(tab2[i] > 0) { if(!ss[i]) { ss[i] = counter; count[counter][1] = i; counter++; } for(int k = 0; k < tab[i].size(); k++) { if(tab2[tab[i][k]] && !ss[tab[i][k]]) { ss[tab[i][k]] = ss[i]; } } } } for(int i = 1; i <= n; i++) { count[ss[i]][0]++; } int max = 0; int imax = 0; for(int i = 1; i < counter; i++) { if(count[i][0] > max) { max = count[i][0]; imax = i; } } if(max == 0) printf("NIE\n"); else { printf("%d\n", max); for(int i = 1; i <= n; i++) if(ss[i] == imax) printf("%d ", i); printf("\n"); } }
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 | #include<iostream> #include<cstdio> #include<vector> using namespace std; int n, m, d; vector<int> tab[200001]; int tab2[200001]; int ss[200001]; int count[200001][2]; main() { scanf("%d %d %d", &n, &m, &d); for(int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); tab[a].push_back(b); tab[b].push_back(a); tab2[a]++; tab2[b]++; } bool enough = false; while(!enough) { enough = true; for(int i = 1; i <= n; i++) { if(tab2[i] != 0 && tab2[i] < d) { tab2[i] = 0; for(int k = 0; k < tab[i].size(); k++) { if(tab2[tab[i][k]]) { tab2[tab[i][k]]--; } } enough = false; } } } int counter = 1; for(int i = 1; i <= n; i++) { if(tab2[i] > 0) { if(!ss[i]) { ss[i] = counter; count[counter][1] = i; counter++; } for(int k = 0; k < tab[i].size(); k++) { if(tab2[tab[i][k]] && !ss[tab[i][k]]) { ss[tab[i][k]] = ss[i]; } } } } for(int i = 1; i <= n; i++) { count[ss[i]][0]++; } int max = 0; int imax = 0; for(int i = 1; i < counter; i++) { if(count[i][0] > max) { max = count[i][0]; imax = i; } } if(max == 0) printf("NIE\n"); else { printf("%d\n", max); for(int i = 1; i <= n; i++) if(ss[i] == imax) printf("%d ", i); printf("\n"); } } |