#include <iostream> #include <cstring> #include <queue> #include <vector> #include <list> using namespace std; const int SIZE = 200000+5; vector<int> graph[SIZE]; list<int> lista; bool toVisit[SIZE], visited[SIZE]; int neigh[SIZE]; int n, m, d; void del(int s) { queue<int> Q; Q.push(s); toVisit[s] = false; visited[s] = true; neigh[s] = 0; for(int i=0; i<graph[s].size(); ++i) neigh[graph[s][i]]--; while(!Q.empty()) { int v = Q.front(); Q.pop(); for(int i=0; i<graph[v].size(); ++i) { if(neigh[graph[v][i]] < d && visited[graph[v][i]] == false) { visited[graph[v][i]] = true; Q.push(graph[v][i]); neigh[graph[v][i]] = 0; for(int j=0; j<graph[graph[v][i]].size(); ++j) neigh[graph[v][j]]--; } } } } void searchGraph(int s) { lista.clear(); queue<int> Q; Q.push(s); lista.push_back(s); visited[s] = true; while(!Q.empty()) { int v = Q.front(); Q.pop(); for(int i=0; i<graph[v].size(); ++i) { if(visited[graph[v][i]] == false && neigh[graph[v][i]] >= d && toVisit[graph[v][i]] == true) { visited[graph[v][i]] = true; Q.push(graph[v][i]); lista.push_back(graph[v][i]); } } } } int main() { ios_base::sync_with_stdio(false); memset(toVisit, true, sizeof(toVisit)); memset(visited, false, sizeof(visited)); cin >> n >> m >> d; int a, b; for(int i=1; i<=m; ++i) { cin >> a >> b; graph[a].push_back(b); graph[b].push_back(a); neigh[a]++; neigh[b]++; } for(int i=1; i<=n; ++i) if(neigh[i] < d && toVisit[i] == true) del(i); memset(visited, false, sizeof(visited)); int out = 0; list<int> outList; for(int i=1; i<=n; ++i) { if(toVisit[i] == true && visited[i] == false && neigh[i] >= d) { searchGraph(i); if(out < lista.size() && lista.size() >= d) { out = lista.size(); outList = lista; } } } if(out < d) cout << "NIE" << endl; else { cout << outList.size() << endl; outList.sort(); for(list<int>::iterator it=outList.begin(); outList.end()!=it; ++it) cout << *it << " "; } cout << endl; 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 | #include <iostream> #include <cstring> #include <queue> #include <vector> #include <list> using namespace std; const int SIZE = 200000+5; vector<int> graph[SIZE]; list<int> lista; bool toVisit[SIZE], visited[SIZE]; int neigh[SIZE]; int n, m, d; void del(int s) { queue<int> Q; Q.push(s); toVisit[s] = false; visited[s] = true; neigh[s] = 0; for(int i=0; i<graph[s].size(); ++i) neigh[graph[s][i]]--; while(!Q.empty()) { int v = Q.front(); Q.pop(); for(int i=0; i<graph[v].size(); ++i) { if(neigh[graph[v][i]] < d && visited[graph[v][i]] == false) { visited[graph[v][i]] = true; Q.push(graph[v][i]); neigh[graph[v][i]] = 0; for(int j=0; j<graph[graph[v][i]].size(); ++j) neigh[graph[v][j]]--; } } } } void searchGraph(int s) { lista.clear(); queue<int> Q; Q.push(s); lista.push_back(s); visited[s] = true; while(!Q.empty()) { int v = Q.front(); Q.pop(); for(int i=0; i<graph[v].size(); ++i) { if(visited[graph[v][i]] == false && neigh[graph[v][i]] >= d && toVisit[graph[v][i]] == true) { visited[graph[v][i]] = true; Q.push(graph[v][i]); lista.push_back(graph[v][i]); } } } } int main() { ios_base::sync_with_stdio(false); memset(toVisit, true, sizeof(toVisit)); memset(visited, false, sizeof(visited)); cin >> n >> m >> d; int a, b; for(int i=1; i<=m; ++i) { cin >> a >> b; graph[a].push_back(b); graph[b].push_back(a); neigh[a]++; neigh[b]++; } for(int i=1; i<=n; ++i) if(neigh[i] < d && toVisit[i] == true) del(i); memset(visited, false, sizeof(visited)); int out = 0; list<int> outList; for(int i=1; i<=n; ++i) { if(toVisit[i] == true && visited[i] == false && neigh[i] >= d) { searchGraph(i); if(out < lista.size() && lista.size() >= d) { out = lista.size(); outList = lista; } } } if(out < d) cout << "NIE" << endl; else { cout << outList.size() << endl; outList.sort(); for(list<int>::iterator it=outList.begin(); outList.end()!=it; ++it) cout << *it << " "; } cout << endl; return 0; } |