#include <cstdio> #include <iostream> #include <algorithm> #include <vector> #include <set> using namespace std; typedef long long LL; typedef vector<int> VI; typedef set<int> SI; typedef pair<int, int> PII; typedef set<PII> SII; #define FOR(i,a,b) for (int i = a; i <= b; ++i) #define FORD(i,a,b) for (int i = a; i >= b; --i) #define REP(i,n) for (int i = 0; i < n; ++i) #define FORE(i,a) for(__typeof(a.begin()) i=a.begin();i!=a.end();++i) #define MP make_pair #define ST first #define ND second #define PB push_back #define MAXN 200007 #define DEBUG false SI g[MAXN]; int deg[MAXN] = {0}; int n, m, d; bool vis[MAXN] = {false}; int ile[MAXN] = {0}; int nss = 0; VI ss[MAXN]; VI *akt_ss; void dfs(int r) { if (!vis[r]) { vis[r] = true; akt_ss->PB(r); ile[nss]++; FORE(sas, g[r]) dfs(*sas); } } int main() { scanf("%d%d%d", &n, &m, &d); int a, b; REP(i, m) { scanf("%d%d", &a, &b); g[a].insert(b); g[b].insert(a); deg[a]++; deg[b]++; } SII s; FOR (i, 1, n) { s.insert(MP(deg[i], i)); } REP (jj, n) { int x = s.begin()->ND; s.erase(s.begin()); if (deg[x] >= d) break; FORE(sas, g[x]) { s.erase(MP(deg[*sas], *sas)); g[*sas].erase(x); deg[*sas]--; s.insert(MP(deg[*sas], *sas)); } deg[x] = 0; g[x].clear(); } int best_ss = -1; int best_nr = -1; FOR(i, 1, n) { if (!vis[i]) { akt_ss = &ss[nss]; ile[nss] = 0; dfs(i); if (ile[nss] > best_ss) { best_nr = nss; best_ss = ile[nss]; } nss++; } } sort(ss[best_nr].begin(), ss[best_nr].end()); if (best_ss == 1) printf("NIE"); else { printf("%d\n", best_ss); REP(i, best_ss) printf("%d ", ss[best_nr][i]); } 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 <cstdio> #include <iostream> #include <algorithm> #include <vector> #include <set> using namespace std; typedef long long LL; typedef vector<int> VI; typedef set<int> SI; typedef pair<int, int> PII; typedef set<PII> SII; #define FOR(i,a,b) for (int i = a; i <= b; ++i) #define FORD(i,a,b) for (int i = a; i >= b; --i) #define REP(i,n) for (int i = 0; i < n; ++i) #define FORE(i,a) for(__typeof(a.begin()) i=a.begin();i!=a.end();++i) #define MP make_pair #define ST first #define ND second #define PB push_back #define MAXN 200007 #define DEBUG false SI g[MAXN]; int deg[MAXN] = {0}; int n, m, d; bool vis[MAXN] = {false}; int ile[MAXN] = {0}; int nss = 0; VI ss[MAXN]; VI *akt_ss; void dfs(int r) { if (!vis[r]) { vis[r] = true; akt_ss->PB(r); ile[nss]++; FORE(sas, g[r]) dfs(*sas); } } int main() { scanf("%d%d%d", &n, &m, &d); int a, b; REP(i, m) { scanf("%d%d", &a, &b); g[a].insert(b); g[b].insert(a); deg[a]++; deg[b]++; } SII s; FOR (i, 1, n) { s.insert(MP(deg[i], i)); } REP (jj, n) { int x = s.begin()->ND; s.erase(s.begin()); if (deg[x] >= d) break; FORE(sas, g[x]) { s.erase(MP(deg[*sas], *sas)); g[*sas].erase(x); deg[*sas]--; s.insert(MP(deg[*sas], *sas)); } deg[x] = 0; g[x].clear(); } int best_ss = -1; int best_nr = -1; FOR(i, 1, n) { if (!vis[i]) { akt_ss = &ss[nss]; ile[nss] = 0; dfs(i); if (ile[nss] > best_ss) { best_nr = nss; best_ss = ile[nss]; } nss++; } } sort(ss[best_nr].begin(), ss[best_nr].end()); if (best_ss == 1) printf("NIE"); else { printf("%d\n", best_ss); REP(i, best_ss) printf("%d ", ss[best_nr][i]); } return 0; } |