#include <cstdio> //#include <iostream> #include <vector> #include <queue> //#pragma warning(disable : 4996) #define SIZE 200000 using namespace std; vector<int> N[SIZE + 1]; int ID[SIZE + 1]; int n, m, d; queue<int> invalid; queue<int> to_check; bool was_inserted[SIZE + 1]; int Size[SIZE + 1]; int mx_id = 0; void DFS(int v, int id) { ID[v] = id; for (int i = 0; i < N[v].size(); i++) { if (N[N[v][i]].size() >= d && ID[N[v][i]] != id) DFS(N[v][i], id); } } int main() { scanf("%d %d %d", &n, &m, &d); for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); N[a].push_back(b); N[b].push_back(a); } for (int i = 1; i <= n; i++) { was_inserted[i] = false; Size[i] = 0; if (N[i].size() < d) invalid.push(i); } while (!invalid.empty()) { while (!invalid.empty()) { int id = invalid.front(); invalid.pop(); for (int i = 0; i < N[id].size(); i++) { int u = N[id][i]; if (!was_inserted[u]) { was_inserted[u] = true; to_check.push(u); } } N[id].clear(); } while (!to_check.empty()) { int id = to_check.front(); to_check.pop(); was_inserted[id] = false; int i = 0; while(i < N[id].size()) { //int u = N[id][i]; if (N[N[id][i]].size() < d) { N[id][i]=N[id].back(); N[id].pop_back(); } else i++; } if (N[id].size() < d) invalid.push(id); } } for (int i = 1; i <= n; i++) { if (ID[i] == 0 && N[i].size() >= d) DFS(i, i); } //for (int i = 0; i <= n; i++) // std::cerr << i << "(" << ID[i] << "); "; //std::cerr << "\n"; for (int i = 1; i <= n; i++) { Size[ID[i]]+=(ID[i]!=0?1:0); mx_id = (Size[mx_id] < Size[ID[i]] ? ID[i] : mx_id); } if (Size[mx_id] < 2) { printf("NIE"); return 0; } printf("%d\n", Size[mx_id]); for (int i = 0; i <= n; i++) { if (ID[i] == mx_id) printf("%d ", i); } 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 | #include <cstdio> //#include <iostream> #include <vector> #include <queue> //#pragma warning(disable : 4996) #define SIZE 200000 using namespace std; vector<int> N[SIZE + 1]; int ID[SIZE + 1]; int n, m, d; queue<int> invalid; queue<int> to_check; bool was_inserted[SIZE + 1]; int Size[SIZE + 1]; int mx_id = 0; void DFS(int v, int id) { ID[v] = id; for (int i = 0; i < N[v].size(); i++) { if (N[N[v][i]].size() >= d && ID[N[v][i]] != id) DFS(N[v][i], id); } } int main() { scanf("%d %d %d", &n, &m, &d); for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); N[a].push_back(b); N[b].push_back(a); } for (int i = 1; i <= n; i++) { was_inserted[i] = false; Size[i] = 0; if (N[i].size() < d) invalid.push(i); } while (!invalid.empty()) { while (!invalid.empty()) { int id = invalid.front(); invalid.pop(); for (int i = 0; i < N[id].size(); i++) { int u = N[id][i]; if (!was_inserted[u]) { was_inserted[u] = true; to_check.push(u); } } N[id].clear(); } while (!to_check.empty()) { int id = to_check.front(); to_check.pop(); was_inserted[id] = false; int i = 0; while(i < N[id].size()) { //int u = N[id][i]; if (N[N[id][i]].size() < d) { N[id][i]=N[id].back(); N[id].pop_back(); } else i++; } if (N[id].size() < d) invalid.push(id); } } for (int i = 1; i <= n; i++) { if (ID[i] == 0 && N[i].size() >= d) DFS(i, i); } //for (int i = 0; i <= n; i++) // std::cerr << i << "(" << ID[i] << "); "; //std::cerr << "\n"; for (int i = 1; i <= n; i++) { Size[ID[i]]+=(ID[i]!=0?1:0); mx_id = (Size[mx_id] < Size[ID[i]] ? ID[i] : mx_id); } if (Size[mx_id] < 2) { printf("NIE"); return 0; } printf("%d\n", Size[mx_id]); for (int i = 0; i <= n; i++) { if (ID[i] == mx_id) printf("%d ", i); } return 0; } |