#include<cstdio> #include<algorithm> #include<vector> #include<queue> #define FOR(i, b, n) for ( int (i) = b; (i) < (n); (i)++) #define FORR(i, b, n) for ( (i) = b; (i) < (n); (i)++) #define REP(i, n) for ( int (i) = 0; (i) < (n); (i)++) #define SC(n) scanf("%d", &(n)) #define SC2(n, m) scanf("%d%d", &(n), &(m)) #define SCLL(n) scanf("%lld", &(n)) #define PRT(n) printf("%d", (n)) #define SPACE printf(" "); #define PRTLL(n) printf("%lld ", (n)) #define NXL printf("\n") typedef long long LL; typedef unsigned long long ULL; using namespace std; #define st first #define nd second #define pb push_back const int MANY = 2e5+9; vector<int> g[MANY]; bool exists[MANY]; int deg[MANY]; queue<int> q; int ssnum; int ss[MANY]; bool vis[MANY]; vector<int> ans; int findss (int u) { if(!exists[u] || vis[u]) return 0; vis[u] = 1; ss[u] = ssnum; int res = 0; REP(i, g[u].size()) res += findss(g[u][i]); return res+1; } int main() { int n, m, d; SC2(n, m); SC(d); REP(i, n+1) exists[i] = 1; REP(i, m) { int a, b; SC2(a, b); g[a].push_back(b); g[b].push_back(a); deg[a]++; deg[b]++; } REP(i, n+1) if(deg[i] < d) q.push(i); while(!q.empty()) { int t = q.front(); q.pop(); if(!exists[t]) continue; exists[t] = 0; for (int i=0; i<g[t].size(); i++) { int s = g[t][i]; if(exists[s]) { deg[s]--; if(deg[s] < d) q.push(s); } } } bool somethingexists = 0; FOR(i, 1, n+1) if(exists[i]) { somethingexists = 1; break; } if(!somethingexists) { printf("NIE\n"); return 0; } int maxss = 0, which; FOR(i, 1, n+1) { ssnum = i; int sssize = findss(i); if(sssize > maxss) { maxss = sssize; which = i; } } FOR(i, 1, n+1) { if(ss[i] == which) ans.push_back(i); } PRT((int)ans.size()); NXL; REP(i, ans.size()) { PRT(ans[i]); if(i != ans.size() - 1) SPACE; } NXL; 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 121 122 123 124 | #include<cstdio> #include<algorithm> #include<vector> #include<queue> #define FOR(i, b, n) for ( int (i) = b; (i) < (n); (i)++) #define FORR(i, b, n) for ( (i) = b; (i) < (n); (i)++) #define REP(i, n) for ( int (i) = 0; (i) < (n); (i)++) #define SC(n) scanf("%d", &(n)) #define SC2(n, m) scanf("%d%d", &(n), &(m)) #define SCLL(n) scanf("%lld", &(n)) #define PRT(n) printf("%d", (n)) #define SPACE printf(" "); #define PRTLL(n) printf("%lld ", (n)) #define NXL printf("\n") typedef long long LL; typedef unsigned long long ULL; using namespace std; #define st first #define nd second #define pb push_back const int MANY = 2e5+9; vector<int> g[MANY]; bool exists[MANY]; int deg[MANY]; queue<int> q; int ssnum; int ss[MANY]; bool vis[MANY]; vector<int> ans; int findss (int u) { if(!exists[u] || vis[u]) return 0; vis[u] = 1; ss[u] = ssnum; int res = 0; REP(i, g[u].size()) res += findss(g[u][i]); return res+1; } int main() { int n, m, d; SC2(n, m); SC(d); REP(i, n+1) exists[i] = 1; REP(i, m) { int a, b; SC2(a, b); g[a].push_back(b); g[b].push_back(a); deg[a]++; deg[b]++; } REP(i, n+1) if(deg[i] < d) q.push(i); while(!q.empty()) { int t = q.front(); q.pop(); if(!exists[t]) continue; exists[t] = 0; for (int i=0; i<g[t].size(); i++) { int s = g[t][i]; if(exists[s]) { deg[s]--; if(deg[s] < d) q.push(s); } } } bool somethingexists = 0; FOR(i, 1, n+1) if(exists[i]) { somethingexists = 1; break; } if(!somethingexists) { printf("NIE\n"); return 0; } int maxss = 0, which; FOR(i, 1, n+1) { ssnum = i; int sssize = findss(i); if(sssize > maxss) { maxss = sssize; which = i; } } FOR(i, 1, n+1) { if(ss[i] == which) ans.push_back(i); } PRT((int)ans.size()); NXL; REP(i, ans.size()) { PRT(ans[i]); if(i != ans.size() - 1) SPACE; } NXL; return 0; } |