#include <iostream> #include <cstdio> #include <queue> #include <vector> #define For(i, n) for (int i = 0; i < (n); i++) #define ForD(i, n) for (int i = (n) - 1; i >= 0; i--) using namespace std; const int N = 200 * 1000 + 10; vector<int> Graph[N]; int visited[N]; bool forbidden[N]; int forbiddenNeighs[N]; int tickOccurs[N]; void dfs(int x, int tick) { if (visited[x] or forbidden[x]) return; visited[x] = tick; tickOccurs[tick]++; For (i, Graph[x].size()) dfs(Graph[x][i], tick); } int getBestTick(int maxTick) { int max = 0; int tick = 0; for (int i = 1; i < maxTick; i++) if (tickOccurs[i] > max) { max = tickOccurs[i]; tick = i; } return tick; } void printSolution(int tick, int n) { if (tick == 0) { printf("NIE\n"); return; } printf("%d\n", tickOccurs[tick]); For (i, n) if (visited[i + 1] == tick) printf("%d ", i + 1); } void FindForbiddenVerts(int n, int d) { queue<int> Q; bool wasInQ[N] = {0}; For (i, n) if (Graph[i + 1].size() < d) { Q.push(i + 1); wasInQ[i + 1] = true; } while (Q.size()) { int v = Q.front(); Q.pop(); forbidden[v] = true; For (i, Graph[v].size()) if (!wasInQ[Graph[v][i]] and Graph[Graph[v][i]].size() - ++forbiddenNeighs[Graph[v][i]] < d) { Q.push(Graph[v][i]); wasInQ[Graph[v][i]] = true; } } } int main() { int n, m, d; scanf("%d %d %d", &n, &m, &d); For (i, m) { int a, b; scanf("%d %d", &a, &b); Graph[a].push_back(b); Graph[b].push_back(a); } FindForbiddenVerts(n, d); int tick = 1; For (i, n) if (!visited[i + 1]) dfs(i + 1, tick++); printSolution(getBestTick(tick), 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 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 | #include <iostream> #include <cstdio> #include <queue> #include <vector> #define For(i, n) for (int i = 0; i < (n); i++) #define ForD(i, n) for (int i = (n) - 1; i >= 0; i--) using namespace std; const int N = 200 * 1000 + 10; vector<int> Graph[N]; int visited[N]; bool forbidden[N]; int forbiddenNeighs[N]; int tickOccurs[N]; void dfs(int x, int tick) { if (visited[x] or forbidden[x]) return; visited[x] = tick; tickOccurs[tick]++; For (i, Graph[x].size()) dfs(Graph[x][i], tick); } int getBestTick(int maxTick) { int max = 0; int tick = 0; for (int i = 1; i < maxTick; i++) if (tickOccurs[i] > max) { max = tickOccurs[i]; tick = i; } return tick; } void printSolution(int tick, int n) { if (tick == 0) { printf("NIE\n"); return; } printf("%d\n", tickOccurs[tick]); For (i, n) if (visited[i + 1] == tick) printf("%d ", i + 1); } void FindForbiddenVerts(int n, int d) { queue<int> Q; bool wasInQ[N] = {0}; For (i, n) if (Graph[i + 1].size() < d) { Q.push(i + 1); wasInQ[i + 1] = true; } while (Q.size()) { int v = Q.front(); Q.pop(); forbidden[v] = true; For (i, Graph[v].size()) if (!wasInQ[Graph[v][i]] and Graph[Graph[v][i]].size() - ++forbiddenNeighs[Graph[v][i]] < d) { Q.push(Graph[v][i]); wasInQ[Graph[v][i]] = true; } } } int main() { int n, m, d; scanf("%d %d %d", &n, &m, &d); For (i, m) { int a, b; scanf("%d %d", &a, &b); Graph[a].push_back(b); Graph[b].push_back(a); } FindForbiddenVerts(n, d); int tick = 1; For (i, n) if (!visited[i + 1]) dfs(i + 1, tick++); printSolution(getBestTick(tick), n); return 0; } |