#include <vector> #include <iostream> #include <sstream> #include <math.h> #include <sys/time.h> #include <cstdlib> #include <algorithm> #include <cassert> #include <cstring> #include <fstream> #include <set> #include <set> #define FOR(i,a,b) for(__typeof(b) i=(a);i<(b);++i) #define REP(i,a) FOR(i,0,a) #define FOREACH(x,c) for(__typeof(c.begin()) x=c.begin();x != c.end(); x++) #define ALL(c) c.begin(),c.end() #define CLEAR(c) memset(c,0,sizeof(c)) #define SIZE(c) (int) ((c).size()) #define PB push_back #define MP make_pair #define X first #define Y second #define ULL unsigned long long #define LL long long #define LD long double #define II pair<int, int> #define DD pair<double, double> #define VC vector #define VI VC<int> #define VVI VC<VI> #define VD VC<double> #define VS VC<string> #define VII VC<II> #define VDD VC<DD> #define DB(a) cerr << #a << ": " << a << endl; using namespace std; template<class T> void print(VC < T > v) {cerr << "[";if (SIZE(v) != 0) cerr << v[0]; FOR(i, 1, SIZE(v)) cerr << "," << v[i]; cerr << "]\n";} template<class T> string i2s(T &x) { ostringstream o; o << x; return o.str(); } VS split(string &s, char c = ' ') {VS all; int p = 0, np; while (np = s.find(c, p), np >= 0) {if (np != p) all.PB(s.substr(p, np - p)); p = np + 1;} if (p < SIZE(s)) all.PB(s.substr(p)); return all;} int n,m,d; VVI G; VI deg; void readData(){ scanf("%d %d %d",&n,&m,&d); G.resize(n); deg.resize(n,0); int a,b; REP(i,m){ scanf("%d %d",&a,&b); G[a-1].PB(b-1); deg[a-1]++; G[b-1].PB(a-1); deg[b-1]++; } } set<II> deleted; void trim(){ VI del; REP(i,n) if (deg[i] < d) del.PB(i); while (!del.empty()){ int v = del.back(); del.pop_back(); for(auto u : G[v]) if (deleted.find(MP(v,u)) == deleted.end()){ deleted.insert(MP(u,v)); deg[u]--; if (deg[u] == d-1) del.PB(u); } G[v].clear(); deg[v] = 0; } } VI dfs(){ VI ret; VI comp; VI marked(n,0); VI stack; REP(i,n) if (!marked[i] && deg[i]){ stack.PB(i); marked[i] = 1; comp.PB(i); while(!stack.empty()){ int v = stack.back(); stack.pop_back(); for(auto u : G[v]) if (deleted.find(MP(v,u)) == deleted.end() && !marked[u]){ stack.PB(u); marked[u] = 1; comp.PB(u); } } if (SIZE(comp) > SIZE(ret)) ret = comp; comp.clear(); } return ret; } int main(int argc, char *argv[]){ readData(); trim(); VI answer = dfs(); if (answer.empty()) printf("NIE\n"); else{ sort(ALL(answer)); printf("%d\n",SIZE(answer)); REP(i,SIZE(answer)-1) printf("%d ",answer[i]+1); printf("%d\n",answer.back()+1); } 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 | #include <vector> #include <iostream> #include <sstream> #include <math.h> #include <sys/time.h> #include <cstdlib> #include <algorithm> #include <cassert> #include <cstring> #include <fstream> #include <set> #include <set> #define FOR(i,a,b) for(__typeof(b) i=(a);i<(b);++i) #define REP(i,a) FOR(i,0,a) #define FOREACH(x,c) for(__typeof(c.begin()) x=c.begin();x != c.end(); x++) #define ALL(c) c.begin(),c.end() #define CLEAR(c) memset(c,0,sizeof(c)) #define SIZE(c) (int) ((c).size()) #define PB push_back #define MP make_pair #define X first #define Y second #define ULL unsigned long long #define LL long long #define LD long double #define II pair<int, int> #define DD pair<double, double> #define VC vector #define VI VC<int> #define VVI VC<VI> #define VD VC<double> #define VS VC<string> #define VII VC<II> #define VDD VC<DD> #define DB(a) cerr << #a << ": " << a << endl; using namespace std; template<class T> void print(VC < T > v) {cerr << "[";if (SIZE(v) != 0) cerr << v[0]; FOR(i, 1, SIZE(v)) cerr << "," << v[i]; cerr << "]\n";} template<class T> string i2s(T &x) { ostringstream o; o << x; return o.str(); } VS split(string &s, char c = ' ') {VS all; int p = 0, np; while (np = s.find(c, p), np >= 0) {if (np != p) all.PB(s.substr(p, np - p)); p = np + 1;} if (p < SIZE(s)) all.PB(s.substr(p)); return all;} int n,m,d; VVI G; VI deg; void readData(){ scanf("%d %d %d",&n,&m,&d); G.resize(n); deg.resize(n,0); int a,b; REP(i,m){ scanf("%d %d",&a,&b); G[a-1].PB(b-1); deg[a-1]++; G[b-1].PB(a-1); deg[b-1]++; } } set<II> deleted; void trim(){ VI del; REP(i,n) if (deg[i] < d) del.PB(i); while (!del.empty()){ int v = del.back(); del.pop_back(); for(auto u : G[v]) if (deleted.find(MP(v,u)) == deleted.end()){ deleted.insert(MP(u,v)); deg[u]--; if (deg[u] == d-1) del.PB(u); } G[v].clear(); deg[v] = 0; } } VI dfs(){ VI ret; VI comp; VI marked(n,0); VI stack; REP(i,n) if (!marked[i] && deg[i]){ stack.PB(i); marked[i] = 1; comp.PB(i); while(!stack.empty()){ int v = stack.back(); stack.pop_back(); for(auto u : G[v]) if (deleted.find(MP(v,u)) == deleted.end() && !marked[u]){ stack.PB(u); marked[u] = 1; comp.PB(u); } } if (SIZE(comp) > SIZE(ret)) ret = comp; comp.clear(); } return ret; } int main(int argc, char *argv[]){ readData(); trim(); VI answer = dfs(); if (answer.empty()) printf("NIE\n"); else{ sort(ALL(answer)); printf("%d\n",SIZE(answer)); REP(i,SIZE(answer)-1) printf("%d ",answer[i]+1); printf("%d\n",answer.back()+1); } return 0; } |