// PA 2015, miodziu@poczta.fm #include <cstdio> #include <cstdlib> #include <vector> #include <string> #include <algorithm> #include <queue> #include <set> #include <map> #include <ctime> #include <cmath> using namespace std; typedef vector<int> VI; typedef vector<VI> VVI; typedef pair<int,int> PII; typedef long long LL; typedef vector<LL> VLL; typedef unsigned long long ULL; #define mp make_pair int read() { int n; scanf("%d", &n); return n; } char readc() { char c; scanf("%c", &c); return c; } LL readl() { LL n; scanf("%lld", &n); return n; } #define REP(i,n) for (int i=0,_=(n); i<_; ++i) #define FOR(i,a,b) for (int i=(a),_=(b); i<=_; ++i) #define FORD(i,a,b) for (int i=(a),_=(b); i>=_; --i) #define st first #define nd second class FU { vector<int> p; public: FU(int n) : p(n, -1) {} int f(int x) { int r = x, t; while (p[r] >= 0) r = p[r]; while (x != r) t = p[x], p[x] = r, x = t; return r; } void u(int x, int y) { x = f(x); y = f(y); if (x == y) return; if (p[x] < p[y]) p[x] += p[y], p[y] = x; else p[y] += p[x], p[x] = y; } int s(int x) { return -p[f(x)]; } }; int main() { int n = read(); int m = read(); int d = read(); vector<VI> s(n); VI ile(n, 0); REP(i, m) { int a = read() - 1; int b = read() - 1; s[a].push_back(b); s[b].push_back(a); ile[a]++; ile[b]++; } int res = n; queue<int> q; REP(i, n) if (ile[i] < d) { //printf("start: %d\n", i+1); q.push(i); ile[i] = -1; res--; } while (!q.empty()) { int x = q.front(); //printf("x: %d\n", x); q.pop(); REP(i, s[x].size()) { int y = s[x][i]; if (ile[y] < 0) continue; //printf("y: %d\n", y); ile[y]--; if (ile[y] < d) { q.push(y); ile[y] = -1; res--; } } } //REP(i, n) printf("%d: %d\n", i+1, ile[i]); //return 0; if (res == 0) { printf("NIE\n"); return 0; } FU fu(n+1); REP(i, n) if (ile[i] >= 0) { REP(j, s[i].size()) if (ile[s[i][j]] >= 0) fu.u(i, s[i][j]); } int id = n; REP(i, n) if (ile[i] >= 0) { if (fu.s(i) > fu.s(id)) id = fu.f(i); } printf("%d\n", fu.s(id)); bool next = false; REP(i, n) if (fu.f(i) == id) { if (next) printf(" "); next = true; printf("%d", i+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 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 | // PA 2015, miodziu@poczta.fm #include <cstdio> #include <cstdlib> #include <vector> #include <string> #include <algorithm> #include <queue> #include <set> #include <map> #include <ctime> #include <cmath> using namespace std; typedef vector<int> VI; typedef vector<VI> VVI; typedef pair<int,int> PII; typedef long long LL; typedef vector<LL> VLL; typedef unsigned long long ULL; #define mp make_pair int read() { int n; scanf("%d", &n); return n; } char readc() { char c; scanf("%c", &c); return c; } LL readl() { LL n; scanf("%lld", &n); return n; } #define REP(i,n) for (int i=0,_=(n); i<_; ++i) #define FOR(i,a,b) for (int i=(a),_=(b); i<=_; ++i) #define FORD(i,a,b) for (int i=(a),_=(b); i>=_; --i) #define st first #define nd second class FU { vector<int> p; public: FU(int n) : p(n, -1) {} int f(int x) { int r = x, t; while (p[r] >= 0) r = p[r]; while (x != r) t = p[x], p[x] = r, x = t; return r; } void u(int x, int y) { x = f(x); y = f(y); if (x == y) return; if (p[x] < p[y]) p[x] += p[y], p[y] = x; else p[y] += p[x], p[x] = y; } int s(int x) { return -p[f(x)]; } }; int main() { int n = read(); int m = read(); int d = read(); vector<VI> s(n); VI ile(n, 0); REP(i, m) { int a = read() - 1; int b = read() - 1; s[a].push_back(b); s[b].push_back(a); ile[a]++; ile[b]++; } int res = n; queue<int> q; REP(i, n) if (ile[i] < d) { //printf("start: %d\n", i+1); q.push(i); ile[i] = -1; res--; } while (!q.empty()) { int x = q.front(); //printf("x: %d\n", x); q.pop(); REP(i, s[x].size()) { int y = s[x][i]; if (ile[y] < 0) continue; //printf("y: %d\n", y); ile[y]--; if (ile[y] < d) { q.push(y); ile[y] = -1; res--; } } } //REP(i, n) printf("%d: %d\n", i+1, ile[i]); //return 0; if (res == 0) { printf("NIE\n"); return 0; } FU fu(n+1); REP(i, n) if (ile[i] >= 0) { REP(j, s[i].size()) if (ile[s[i][j]] >= 0) fu.u(i, s[i][j]); } int id = n; REP(i, n) if (ile[i] >= 0) { if (fu.s(i) > fu.s(id)) id = fu.f(i); } printf("%d\n", fu.s(id)); bool next = false; REP(i, n) if (fu.f(i) == id) { if (next) printf(" "); next = true; printf("%d", i+1); } printf("\n"); return 0; } |