#include<cstdio> #include<algorithm> #include<vector> #include<cstring> #include<set> #include<assert.h> using namespace std; #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(i,0,(n)-1) #define RI(i,n) FOR(i,1,n) #define pb push_back #define mp make_pair #define st first #define nd second #define mini(a,b) a=min(a,b) #define maxi(a,b) a=max(a,b) bool debug; typedef vector<int> vi; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; const int inf = 1e9 + 5; const int nax = 2e5 + 5; int n,m,d,a,b; vi dowora, dupa, pom; vector<pii> v[nax]; bool ni_ma_w[nax]; int st[nax]; void dfs(int x) { ni_ma_w[x] = true; pom.pb(x); for (auto w: v[x]) { if (!ni_ma_w[w.st]) { dfs(w.st); } } } int main(int argc, char * argv[]) { debug = argc > 1; scanf("%d%d%d",&n,&m,&d); REP(i,m) { scanf("%d%d",&a,&b); v[a].pb(mp(b,i)); v[b].pb(mp(a,i)); } FOR(i,1,n) st[i] = v[i].size(); FOR(i,1,n) if (st[i] < d) { ni_ma_w[i] = true; dowora.pb(i); } while (!dowora.empty()) { int x = dowora.back(); dowora.pop_back(); for (auto p: v[x]) if (!ni_ma_w[p.st]) { --st[p.st]; if (st[p.st] < d) { ni_ma_w[p.st] = true; dowora.pb(p.st); } } } FOR(i,1,n) if (!ni_ma_w[i]) { pom.clear(); dfs(i); if (pom.size() > dupa.size()) dupa = pom; } sort(dupa.begin(), dupa.end()); if (dupa.empty()) { puts("NIE"); } else { printf("%d\n",(int)dupa.size()); for (auto x: dupa) { printf("%d ",x); } puts(""); } 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 | #include<cstdio> #include<algorithm> #include<vector> #include<cstring> #include<set> #include<assert.h> using namespace std; #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(i,0,(n)-1) #define RI(i,n) FOR(i,1,n) #define pb push_back #define mp make_pair #define st first #define nd second #define mini(a,b) a=min(a,b) #define maxi(a,b) a=max(a,b) bool debug; typedef vector<int> vi; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; const int inf = 1e9 + 5; const int nax = 2e5 + 5; int n,m,d,a,b; vi dowora, dupa, pom; vector<pii> v[nax]; bool ni_ma_w[nax]; int st[nax]; void dfs(int x) { ni_ma_w[x] = true; pom.pb(x); for (auto w: v[x]) { if (!ni_ma_w[w.st]) { dfs(w.st); } } } int main(int argc, char * argv[]) { debug = argc > 1; scanf("%d%d%d",&n,&m,&d); REP(i,m) { scanf("%d%d",&a,&b); v[a].pb(mp(b,i)); v[b].pb(mp(a,i)); } FOR(i,1,n) st[i] = v[i].size(); FOR(i,1,n) if (st[i] < d) { ni_ma_w[i] = true; dowora.pb(i); } while (!dowora.empty()) { int x = dowora.back(); dowora.pop_back(); for (auto p: v[x]) if (!ni_ma_w[p.st]) { --st[p.st]; if (st[p.st] < d) { ni_ma_w[p.st] = true; dowora.pb(p.st); } } } FOR(i,1,n) if (!ni_ma_w[i]) { pom.clear(); dfs(i); if (pom.size() > dupa.size()) dupa = pom; } sort(dupa.begin(), dupa.end()); if (dupa.empty()) { puts("NIE"); } else { printf("%d\n",(int)dupa.size()); for (auto x: dupa) { printf("%d ",x); } puts(""); } return 0; } |