// PA2015, runda 2, mistrzostwa // Andrzej Pezarski #include <cstdio> #include <cstdlib> #include <vector> #include <set> #include <map> #include <stack> #include <algorithm> #include <cassert> using namespace std; int main() { int N, M, D; scanf("%d%d%d", &N, &M, &D); vector<vector<int> > G(N); vector<int> mark(N); vector<int> deg(N); for (int v=0; v<M; v++) { int a, b; scanf("%d%d", &a, &b); deg[--a]++; deg[--b]++; G[a].push_back(b); G[b].push_back(a); } int N0=N; stack<int> S; for (int v=0; v<N; v++) { if (deg[v]<D) { S.push(v); mark[v]=1; N0--; } } while (!S.empty()) { int v=S.top(); S.pop(); for (auto x:G[v]) { if (--deg[x] < D && mark[x] == 0) { mark[x]=1; N0--; S.push(x); } } } if (N0==0) { printf("NIE\n"); return 0; } vector<int> RES; for (int i=0; i<N; i++) if (mark[i]==0) { // printf("brum %d\n", i); mark[i]=1; vector<int> RESt; stack<int> St; St.push(i); while (!St.empty()) { int v=St.top(); St.pop(); RESt.push_back(v); for (auto x:G[v]) { if (mark[x] == 0) { mark[x]=1; St.push(x); } } } if (RES.size()<RESt.size()) { RES.swap(RESt); } } sort(RES.begin(), RES.end()); printf("%d\n", int(RES.size())); for (auto x:RES) printf("%d ", x+1); printf("\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 | // PA2015, runda 2, mistrzostwa // Andrzej Pezarski #include <cstdio> #include <cstdlib> #include <vector> #include <set> #include <map> #include <stack> #include <algorithm> #include <cassert> using namespace std; int main() { int N, M, D; scanf("%d%d%d", &N, &M, &D); vector<vector<int> > G(N); vector<int> mark(N); vector<int> deg(N); for (int v=0; v<M; v++) { int a, b; scanf("%d%d", &a, &b); deg[--a]++; deg[--b]++; G[a].push_back(b); G[b].push_back(a); } int N0=N; stack<int> S; for (int v=0; v<N; v++) { if (deg[v]<D) { S.push(v); mark[v]=1; N0--; } } while (!S.empty()) { int v=S.top(); S.pop(); for (auto x:G[v]) { if (--deg[x] < D && mark[x] == 0) { mark[x]=1; N0--; S.push(x); } } } if (N0==0) { printf("NIE\n"); return 0; } vector<int> RES; for (int i=0; i<N; i++) if (mark[i]==0) { // printf("brum %d\n", i); mark[i]=1; vector<int> RESt; stack<int> St; St.push(i); while (!St.empty()) { int v=St.top(); St.pop(); RESt.push_back(v); for (auto x:G[v]) { if (mark[x] == 0) { mark[x]=1; St.push(x); } } } if (RES.size()<RESt.size()) { RES.swap(RESt); } } sort(RES.begin(), RES.end()); printf("%d\n", int(RES.size())); for (auto x:RES) printf("%d ", x+1); printf("\n"); return 0; } |