#include <iomanip> #include <iostream> #include <utility> #include <algorithm> #include <queue> #include <cassert> #include <string> #include <vector> #include <set> #include <map> using namespace std; #define ALL(x) x.begin(), x.end() #define VAR(a,b) __typeof (b) a = b #define IN(a) int a; cin >> a #define IN2(a,b) int a, b; cin >> a >> b #define REP(i,n) for (int _n=(n), i=0; i<_n; ++i) #define FOR(i,a,b) for (int _b=(b), i=(a); i<=_b; ++i) #define FORD(i,a,b) for (int _b=(b), i=(a); i>=_b; --i) #define FORE(i,a) for (VAR(i,a.begin ()); i!=a.end (); ++i) #define PB push_back #define MP make_pair #define ST first #define ND second typedef vector<int> VI; typedef long long LL; typedef pair<int,int> PII; typedef double LD; const int DBG = 0, INF = int(1e9); int main() { ios_base::sync_with_stdio(0); cout.setf(ios::fixed); int n, m, d; cin >> n >> m >> d; vector<VI> v(n); VI deg(n, 0); REP(q,m) { IN2(a,b); --a; --b; v[a].PB(b); v[b].PB(a); ++deg[a]; ++deg[b]; } queue<int> rem; vector<bool> is_removed(n, false); REP(i,n) if (deg[i] < d) { rem.push(i); is_removed[i] = true; } while (!rem.empty()) { int nxt = rem.front(); rem.pop(); FORE(it, v[nxt]) { if (--deg[*it] < d && !is_removed[*it]) { rem.push(*it); is_removed[*it] = true; } } } set<int> best; vector<int> st; REP(i,n) if (!is_removed[i]) { set<int> cur; cur.insert(i); is_removed[i] = true; st.PB(i); while (!st.empty()) { int nxt = st.back(); st.pop_back(); FORE(it, v[nxt]) if (!is_removed[*it]) { cur.insert(*it); is_removed[*it] = true; st.PB(*it); } } if (cur.size() > best.size()) swap(cur, best); } if (best.empty()) cout << "NIE\n"; else { cout << best.size() << endl; FORE(it, best) cout << *it + 1 << " "; cout << endl; } 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 | #include <iomanip> #include <iostream> #include <utility> #include <algorithm> #include <queue> #include <cassert> #include <string> #include <vector> #include <set> #include <map> using namespace std; #define ALL(x) x.begin(), x.end() #define VAR(a,b) __typeof (b) a = b #define IN(a) int a; cin >> a #define IN2(a,b) int a, b; cin >> a >> b #define REP(i,n) for (int _n=(n), i=0; i<_n; ++i) #define FOR(i,a,b) for (int _b=(b), i=(a); i<=_b; ++i) #define FORD(i,a,b) for (int _b=(b), i=(a); i>=_b; --i) #define FORE(i,a) for (VAR(i,a.begin ()); i!=a.end (); ++i) #define PB push_back #define MP make_pair #define ST first #define ND second typedef vector<int> VI; typedef long long LL; typedef pair<int,int> PII; typedef double LD; const int DBG = 0, INF = int(1e9); int main() { ios_base::sync_with_stdio(0); cout.setf(ios::fixed); int n, m, d; cin >> n >> m >> d; vector<VI> v(n); VI deg(n, 0); REP(q,m) { IN2(a,b); --a; --b; v[a].PB(b); v[b].PB(a); ++deg[a]; ++deg[b]; } queue<int> rem; vector<bool> is_removed(n, false); REP(i,n) if (deg[i] < d) { rem.push(i); is_removed[i] = true; } while (!rem.empty()) { int nxt = rem.front(); rem.pop(); FORE(it, v[nxt]) { if (--deg[*it] < d && !is_removed[*it]) { rem.push(*it); is_removed[*it] = true; } } } set<int> best; vector<int> st; REP(i,n) if (!is_removed[i]) { set<int> cur; cur.insert(i); is_removed[i] = true; st.PB(i); while (!st.empty()) { int nxt = st.back(); st.pop_back(); FORE(it, v[nxt]) if (!is_removed[*it]) { cur.insert(*it); is_removed[*it] = true; st.PB(*it); } } if (cur.size() > best.size()) swap(cur, best); } if (best.empty()) cout << "NIE\n"; else { cout << best.size() << endl; FORE(it, best) cout << *it + 1 << " "; cout << endl; } return 0; } |