#include <bits/stdc++.h> using namespace std; int d, maax; vector<int> G[200000]; int fake[200000]; bool visit[200000]; void chknode(int x, int firstcall) { if ((int)G[x].size() > d - firstcall || fake[x]) return; // fprintf(stderr, "usuwam wierzchołek %d\n", x+1); fake[x]=1; vector<int>::iterator it, it2; for (it = G[x].begin(); it != G[x].end(); it++) { if (fake[*it]) continue; // fprintf(stderr, "usuwam krawędź %d -> %d\n", x+1, *it+1); if (*it < maax) chknode(*it, 0); for (it2 = G[*it].begin(); it2 != G[*it].end(); it2++) { if (*it2 == x) { G[*it].erase(it2); break; } } G[x].erase(--it+1); } } int dfs(int x, bool write) { if (visit[x]^write) return 0; if (write) printf("%d ", x+1); visit[x] ^= true; int ret = 1; for (vector<int>::iterator it = G[x].begin(); it != G[x].end(); it++) ret += dfs(*it, write); return ret; } int main() { int i, n,m, u,v; scanf("%d%d%d", &n, &m, &d); while (m--) { scanf("%d%d", &u, &v); u--; v--; G[u].push_back(v); G[v].push_back(u); } for (maax=0; maax<n; maax++) chknode(maax, 1); int c, bestc = 0, besti = 0; for (i=0; i<n; i++) if (!fake[i]) { c = dfs(i, false); if (c > bestc) { besti = i; bestc = c; } } if (bestc == 0) { puts("NIE"); return 0; } printf("%d\n", bestc); dfs(besti, true); puts(""); 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 | #include <bits/stdc++.h> using namespace std; int d, maax; vector<int> G[200000]; int fake[200000]; bool visit[200000]; void chknode(int x, int firstcall) { if ((int)G[x].size() > d - firstcall || fake[x]) return; // fprintf(stderr, "usuwam wierzchołek %d\n", x+1); fake[x]=1; vector<int>::iterator it, it2; for (it = G[x].begin(); it != G[x].end(); it++) { if (fake[*it]) continue; // fprintf(stderr, "usuwam krawędź %d -> %d\n", x+1, *it+1); if (*it < maax) chknode(*it, 0); for (it2 = G[*it].begin(); it2 != G[*it].end(); it2++) { if (*it2 == x) { G[*it].erase(it2); break; } } G[x].erase(--it+1); } } int dfs(int x, bool write) { if (visit[x]^write) return 0; if (write) printf("%d ", x+1); visit[x] ^= true; int ret = 1; for (vector<int>::iterator it = G[x].begin(); it != G[x].end(); it++) ret += dfs(*it, write); return ret; } int main() { int i, n,m, u,v; scanf("%d%d%d", &n, &m, &d); while (m--) { scanf("%d%d", &u, &v); u--; v--; G[u].push_back(v); G[v].push_back(u); } for (maax=0; maax<n; maax++) chknode(maax, 1); int c, bestc = 0, besti = 0; for (i=0; i<n; i++) if (!fake[i]) { c = dfs(i, false); if (c > bestc) { besti = i; bestc = c; } } if (bestc == 0) { puts("NIE"); return 0; } printf("%d\n", bestc); dfs(besti, true); puts(""); return 0; } |