#include <iostream> #include <algorithm> #include <vector> #include <string> #include <map> #include <set> #include <queue> #include <stack> #include <cmath> #include <cassert> #include <cstring> #include <ext/numeric> using namespace std ; using namespace __gnu_cxx ; typedef long long LL ; typedef pair<int,int> PII ; typedef vector<int> VI ; const int INF = 1e9+100 ; const LL INFLL = (LL)INF * (LL)INF ; #define REP(i,n) for(i=0;i<(n);++i) #define ALL(c) c.begin(),c.end() #define VAR(v,i) __typeof(i) v=(i) #define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();++i) #define CLEAR(t) memset(t,0,sizeof(t)) #define PB push_back #define MP make_pair #define FI first #define SE second template<class T1,class T2> ostream& operator<<(ostream &s, const pair<T1,T2> &x) { s<< "(" << x.FI << "," << x.SE << ")"; return s;} template<class T> ostream& operator<<(ostream &s, const vector<T> &t) { FOREACH(it, t) s << *it << " " ; return s ; } template<class T> ostream& operator<<(ostream &s, const set<T> &t) { FOREACH(it, t) s << *it << " " ; return s ; } template<class T1,class T2> ostream& operator<<(ostream &s, const map<T1, T2> &t) { FOREACH(it, t) s << *it << " " ; return s ; } /////////////////////////////////////////// const int MAXN = 200100 ; VI G[MAXN] ; int degree[MAXN] ; bool removed[MAXN] ; VI subgraph ; void DFS(int u) { removed[u] = true ; subgraph.PB(u) ; FOREACH(it, G[u]) if(!removed[*it]) DFS(*it) ; } int main() { ios_base::sync_with_stdio(0) ; int n, m, d, a, b ; cin >> n >> m >> d ; while(m--) { cin >> a >> b ; G[a].PB(b) ; G[b].PB(a) ; } queue<int> toRemove ; for(int i=1 ; i<=n ; i++) { degree[i] = G[i].size() ; if(degree[i]<d) { removed[i] = true ; toRemove.push(i) ; } } while(!toRemove.empty()) { int u = toRemove.front() ; toRemove.pop() ; FOREACH(it, G[u]) if(!removed[*it]) { degree[*it]-- ; if(degree[*it]<d) { removed[*it] = true ; toRemove.push(*it) ; } } } VI ret ; for(int i=1 ; i<=n ; i++) if(!removed[i]) { subgraph.clear() ; DFS(i) ; if(subgraph.size() > ret.size()) ret=subgraph ; } if(ret.empty()) cout << "NIE" << endl ; else { sort(ALL(ret)) ; cout << ret.size() << endl << ret << endl ; } }
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 | #include <iostream> #include <algorithm> #include <vector> #include <string> #include <map> #include <set> #include <queue> #include <stack> #include <cmath> #include <cassert> #include <cstring> #include <ext/numeric> using namespace std ; using namespace __gnu_cxx ; typedef long long LL ; typedef pair<int,int> PII ; typedef vector<int> VI ; const int INF = 1e9+100 ; const LL INFLL = (LL)INF * (LL)INF ; #define REP(i,n) for(i=0;i<(n);++i) #define ALL(c) c.begin(),c.end() #define VAR(v,i) __typeof(i) v=(i) #define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();++i) #define CLEAR(t) memset(t,0,sizeof(t)) #define PB push_back #define MP make_pair #define FI first #define SE second template<class T1,class T2> ostream& operator<<(ostream &s, const pair<T1,T2> &x) { s<< "(" << x.FI << "," << x.SE << ")"; return s;} template<class T> ostream& operator<<(ostream &s, const vector<T> &t) { FOREACH(it, t) s << *it << " " ; return s ; } template<class T> ostream& operator<<(ostream &s, const set<T> &t) { FOREACH(it, t) s << *it << " " ; return s ; } template<class T1,class T2> ostream& operator<<(ostream &s, const map<T1, T2> &t) { FOREACH(it, t) s << *it << " " ; return s ; } /////////////////////////////////////////// const int MAXN = 200100 ; VI G[MAXN] ; int degree[MAXN] ; bool removed[MAXN] ; VI subgraph ; void DFS(int u) { removed[u] = true ; subgraph.PB(u) ; FOREACH(it, G[u]) if(!removed[*it]) DFS(*it) ; } int main() { ios_base::sync_with_stdio(0) ; int n, m, d, a, b ; cin >> n >> m >> d ; while(m--) { cin >> a >> b ; G[a].PB(b) ; G[b].PB(a) ; } queue<int> toRemove ; for(int i=1 ; i<=n ; i++) { degree[i] = G[i].size() ; if(degree[i]<d) { removed[i] = true ; toRemove.push(i) ; } } while(!toRemove.empty()) { int u = toRemove.front() ; toRemove.pop() ; FOREACH(it, G[u]) if(!removed[*it]) { degree[*it]-- ; if(degree[*it]<d) { removed[*it] = true ; toRemove.push(*it) ; } } } VI ret ; for(int i=1 ; i<=n ; i++) if(!removed[i]) { subgraph.clear() ; DFS(i) ; if(subgraph.size() > ret.size()) ret=subgraph ; } if(ret.empty()) cout << "NIE" << endl ; else { sort(ALL(ret)) ; cout << ret.size() << endl << ret << endl ; } } |