#include<cstdio> #include<vector> #include<queue> #include<algorithm> using namespace std; int tab[200001]; int color[200001]; vector<int> G[200001]; queue<int> Q; int counter; int id = 0; int d; void DFS(int v) { color[v] = id; counter++; for (int u : G[v]) { if(tab[u] >= d && !color[u]) DFS(u); } } int main() { int V; int E; scanf("%d%d%d", &V, &E, &d); for (int i = 0; i < E; i++) { int u; int v; scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); tab[u]++; tab[v]++; } for (int i = 1; i <= V; i++) { if (tab[i] < d) { Q.push(i); } } while(!Q.empty()) { int v = Q.front(); Q.pop(); for (int u : G[v]) { if (tab[u] == d) { Q.push(u); } tab[u]--; } } int result = 0; int identifier = 0; for (int i = 1; i <= V; i++) { if (tab[i] >= d && !color[i]) { counter = 0; id++; DFS(i); if (counter > result) { result = counter; identifier = id; } } } if (result) { printf("%d\n", result); for (int i = 1; i <= V; i++) { if (color[i] == identifier) printf("%d ", i); } printf("\n"); } else { printf("NIE\n"); } 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 | #include<cstdio> #include<vector> #include<queue> #include<algorithm> using namespace std; int tab[200001]; int color[200001]; vector<int> G[200001]; queue<int> Q; int counter; int id = 0; int d; void DFS(int v) { color[v] = id; counter++; for (int u : G[v]) { if(tab[u] >= d && !color[u]) DFS(u); } } int main() { int V; int E; scanf("%d%d%d", &V, &E, &d); for (int i = 0; i < E; i++) { int u; int v; scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); tab[u]++; tab[v]++; } for (int i = 1; i <= V; i++) { if (tab[i] < d) { Q.push(i); } } while(!Q.empty()) { int v = Q.front(); Q.pop(); for (int u : G[v]) { if (tab[u] == d) { Q.push(u); } tab[u]--; } } int result = 0; int identifier = 0; for (int i = 1; i <= V; i++) { if (tab[i] >= d && !color[i]) { counter = 0; id++; DFS(i); if (counter > result) { result = counter; identifier = id; } } } if (result) { printf("%d\n", result); for (int i = 1; i <= V; i++) { if (color[i] == identifier) printf("%d ", i); } printf("\n"); } else { printf("NIE\n"); } return 0; } |