#include <cstdio> #include <iostream> #include <vector> #include <list> #include <string> #include <set> #include <map> #include <algorithm> #include <utility> #include <cmath> #include <queue> #include <stack> #include <cassert> #include <cstring> #include <climits> #include <functional> #include <unordered_set> #include <unordered_map> #define VAR(i,v) __typeof(v) i = (v) #define SIZE(x) ((int)(x).size()) #define ALL(x) (x).begin(), (x).end() #define REP(i,b) for(int i=0; i<(b); ++i) #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 FOREACH(i,c) for(VAR(i,(c).begin()); i != (c).end(); ++i) #define PB push_back #define MP make_pair #define ST first #define ND second #define NL printf("\n") using namespace std; typedef pair<int,int> PII; typedef vector<int> VI; typedef long long LL; const int INF = 2147483640; const int MAXN = 1000005; set<int> g[MAXN]; multiset<PII> S; bool vis[MAXN]; int n, m, d; VI vert; void dfs(int u) { vis[u] = 1; vert.PB(u); for(int x: g[u]) if(!vis[x]) dfs(x); } int main() { scanf("%d %d %d", &n, &m, &d); REP(i,m) { int a, b; scanf("%d %d", &a, &b); g[a].insert(b); g[b].insert(a); } FOR(i,1,n) S.insert(MP(SIZE(g[i]),i)); while(!S.empty() && S.begin()->ST < d) { auto u = *S.begin(); S.erase(S.begin()); vis[u.ND] = 1; for(int x: g[u.ND]) { S.erase(S.find(MP(SIZE(g[x]),x))); g[x].erase(g[x].find(u.ND)); if(!g[x].empty()) S.insert(MP(SIZE(g[x]),x)); else vis[x] = 1; } g[u.ND].clear(); } VI res; FOR(i,1,n) if(!vis[i]) { vert.clear(); dfs(i); if(SIZE(vert) > SIZE(res)) res = vert; } sort(ALL(res)); if(!res.empty()) { printf("%d\n", SIZE(res)); for(int x: res) printf("%d ", x); NL; } else { printf("NIE\n"); } 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 | #include <cstdio> #include <iostream> #include <vector> #include <list> #include <string> #include <set> #include <map> #include <algorithm> #include <utility> #include <cmath> #include <queue> #include <stack> #include <cassert> #include <cstring> #include <climits> #include <functional> #include <unordered_set> #include <unordered_map> #define VAR(i,v) __typeof(v) i = (v) #define SIZE(x) ((int)(x).size()) #define ALL(x) (x).begin(), (x).end() #define REP(i,b) for(int i=0; i<(b); ++i) #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 FOREACH(i,c) for(VAR(i,(c).begin()); i != (c).end(); ++i) #define PB push_back #define MP make_pair #define ST first #define ND second #define NL printf("\n") using namespace std; typedef pair<int,int> PII; typedef vector<int> VI; typedef long long LL; const int INF = 2147483640; const int MAXN = 1000005; set<int> g[MAXN]; multiset<PII> S; bool vis[MAXN]; int n, m, d; VI vert; void dfs(int u) { vis[u] = 1; vert.PB(u); for(int x: g[u]) if(!vis[x]) dfs(x); } int main() { scanf("%d %d %d", &n, &m, &d); REP(i,m) { int a, b; scanf("%d %d", &a, &b); g[a].insert(b); g[b].insert(a); } FOR(i,1,n) S.insert(MP(SIZE(g[i]),i)); while(!S.empty() && S.begin()->ST < d) { auto u = *S.begin(); S.erase(S.begin()); vis[u.ND] = 1; for(int x: g[u.ND]) { S.erase(S.find(MP(SIZE(g[x]),x))); g[x].erase(g[x].find(u.ND)); if(!g[x].empty()) S.insert(MP(SIZE(g[x]),x)); else vis[x] = 1; } g[u.ND].clear(); } VI res; FOR(i,1,n) if(!vis[i]) { vert.clear(); dfs(i); if(SIZE(vert) > SIZE(res)) res = vert; } sort(ALL(res)); if(!res.empty()) { printf("%d\n", SIZE(res)); for(int x: res) printf("%d ", x); NL; } else { printf("NIE\n"); } return 0; } |