#include <cstdio> #include <algorithm> #include <set> #include <queue> using namespace std; typedef pair<int, int> pii; struct wp { set <int> s; int odw; }t[200005]; queue <int> q; set <pii> s; int main () { pii pom, prz; int n, m, d, x, y, kol=1, roz=0, numer, wiel; set<pii>::iterator sz; scanf ("%d%d%d", &n, &m, &d); for (int i=0; i<m; i++) { scanf ("%d%d", &x, &y); t[x].s.insert(y); t[y].s.insert(x); } for (int i=1; i<=n; i++) if (t[i].s.size()) s.insert(make_pair(t[i].s.size(), i)); while (!s.empty()&& s.begin()->first<d) { pom=*s.begin(); s.erase(s.begin()); for (set<int>::iterator it=t[pom.second].s.begin(); it!=t[pom.second].s.end(); it++) { sz=s.find(make_pair(t[*it].s.size(), *it)); if (sz!=s.end()) { prz=*sz; s.erase(sz); t[prz.second].s.erase(pom.second); if (prz.first-1>0) s.insert(make_pair(prz.first-1, prz.second)); } } t[pom.second].s.clear(); } /*printf ("poczatek s :\n"); for (set<pii>::iterator it=s.begin(); it!=s.end(); it++) printf ("%d %d\n", it->first, it->second); printf ("koniec s\n"); for (int i=1; i<=n; i++) { printf ("%d : ", i); for (set<int>::iterator it=t[i].s.begin(); it!=t[i].s.end(); it++) printf ("%d ", *it); printf ("\n"); }*/ for (int i=1; i<=n; i++) { if (t[i].odw==0) { wiel=1; q.push(i); t[i].odw=kol; while (!q.empty()) { x=q.front(); q.pop(); for (set<int>::iterator it=t[x].s.begin(); it!=t[x].s.end(); it++) { if (t[*it].odw==0) { q.push(*it); t[*it].odw=kol; wiel++; } } } if (wiel>roz) { roz=wiel; numer=i; } kol++; } } if (s.size()==0) printf ("NIE"); else { printf ("%d\n", roz); for (int i=1; i<=n; i++) if (numer==t[i].odw) printf ("%d ", i); } return 0; } /* 9 14 3 1 9 1 5 1 4 5 9 8 3 7 3 2 3 2 8 5 4 9 6 6 2 4 9 2 7 7 8 10 17 3 1 9 1 5 1 4 5 9 8 3 7 3 2 3 2 8 5 4 9 6 6 2 4 9 2 7 7 8 2 10 7 10 10 3 */
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 130 131 | #include <cstdio> #include <algorithm> #include <set> #include <queue> using namespace std; typedef pair<int, int> pii; struct wp { set <int> s; int odw; }t[200005]; queue <int> q; set <pii> s; int main () { pii pom, prz; int n, m, d, x, y, kol=1, roz=0, numer, wiel; set<pii>::iterator sz; scanf ("%d%d%d", &n, &m, &d); for (int i=0; i<m; i++) { scanf ("%d%d", &x, &y); t[x].s.insert(y); t[y].s.insert(x); } for (int i=1; i<=n; i++) if (t[i].s.size()) s.insert(make_pair(t[i].s.size(), i)); while (!s.empty()&& s.begin()->first<d) { pom=*s.begin(); s.erase(s.begin()); for (set<int>::iterator it=t[pom.second].s.begin(); it!=t[pom.second].s.end(); it++) { sz=s.find(make_pair(t[*it].s.size(), *it)); if (sz!=s.end()) { prz=*sz; s.erase(sz); t[prz.second].s.erase(pom.second); if (prz.first-1>0) s.insert(make_pair(prz.first-1, prz.second)); } } t[pom.second].s.clear(); } /*printf ("poczatek s :\n"); for (set<pii>::iterator it=s.begin(); it!=s.end(); it++) printf ("%d %d\n", it->first, it->second); printf ("koniec s\n"); for (int i=1; i<=n; i++) { printf ("%d : ", i); for (set<int>::iterator it=t[i].s.begin(); it!=t[i].s.end(); it++) printf ("%d ", *it); printf ("\n"); }*/ for (int i=1; i<=n; i++) { if (t[i].odw==0) { wiel=1; q.push(i); t[i].odw=kol; while (!q.empty()) { x=q.front(); q.pop(); for (set<int>::iterator it=t[x].s.begin(); it!=t[x].s.end(); it++) { if (t[*it].odw==0) { q.push(*it); t[*it].odw=kol; wiel++; } } } if (wiel>roz) { roz=wiel; numer=i; } kol++; } } if (s.size()==0) printf ("NIE"); else { printf ("%d\n", roz); for (int i=1; i<=n; i++) if (numer==t[i].odw) printf ("%d ", i); } return 0; } /* 9 14 3 1 9 1 5 1 4 5 9 8 3 7 3 2 3 2 8 5 4 9 6 6 2 4 9 2 7 7 8 10 17 3 1 9 1 5 1 4 5 9 8 3 7 3 2 3 2 8 5 4 9 6 6 2 4 9 2 7 7 8 2 10 7 10 10 3 */ |