#include <cstdio> #include <vector> #include <forward_list> #include <unordered_set> using namespace std; void removeLessThanD(int v, vector<forward_list<int> > &ve, int d, unordered_set<int> &ds) { if (ds.find(v) == ds.end()) { return; } int count = 0; for (auto it = ve[v].begin(); it != ve[v].end(); ++it) { if (ds.find(*it) != ds.end()) { ++count; } } if (count < d) { ds.erase(v); for (auto it = ve[v].begin(); it != ve[v].end(); ++it) { removeLessThanD(*it, ve, d, ds); } } } int dfs(int v, vector<forward_list<int> > &ve, unordered_set<int> ¬Visited, forward_list<int> &visited) { if (notVisited.find(v) == notVisited.end()) { return 0; } notVisited.erase(v); visited.push_front(v); int count = 1; for (auto it = ve[v].begin(); it != ve[v].end(); ++it) { count += dfs(*it, ve, notVisited, visited); } return count; } int main() { int n, m, d; scanf("%d %d %d", &n, &m, &d); vector<forward_list<int> > ve (n, forward_list<int>()); for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); --a; --b; ve[a].push_front(b); ve[b].push_front(a); } unordered_set<int> ds; for (int i = 0; i < n; i++) { ds.insert (i); } for (int i = 0; i < ve.size(); ++i) { removeLessThanD(i, ve, d, ds); } unordered_set<int> notVisited (ds); if (notVisited.empty()) { printf("NIE"); } else { int maxVisitedCount = 0; forward_list<int> maxVisited; while (!notVisited.empty()) { int notVisitedSizeBefore = notVisited.size(); forward_list<int> visited; dfs(*notVisited.begin(), ve, notVisited, visited); int notVisitedSizeAfter = notVisited.size(); int visitedCount = notVisitedSizeBefore - notVisitedSizeAfter; if (visitedCount > maxVisitedCount) { maxVisitedCount = visitedCount; maxVisited = visited; } } maxVisited.sort(); printf("%d\n", maxVisitedCount); for (auto it = maxVisited.begin(); it != maxVisited.end(); ++it) { printf("%d ", (*it)+1); } } 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 | #include <cstdio> #include <vector> #include <forward_list> #include <unordered_set> using namespace std; void removeLessThanD(int v, vector<forward_list<int> > &ve, int d, unordered_set<int> &ds) { if (ds.find(v) == ds.end()) { return; } int count = 0; for (auto it = ve[v].begin(); it != ve[v].end(); ++it) { if (ds.find(*it) != ds.end()) { ++count; } } if (count < d) { ds.erase(v); for (auto it = ve[v].begin(); it != ve[v].end(); ++it) { removeLessThanD(*it, ve, d, ds); } } } int dfs(int v, vector<forward_list<int> > &ve, unordered_set<int> ¬Visited, forward_list<int> &visited) { if (notVisited.find(v) == notVisited.end()) { return 0; } notVisited.erase(v); visited.push_front(v); int count = 1; for (auto it = ve[v].begin(); it != ve[v].end(); ++it) { count += dfs(*it, ve, notVisited, visited); } return count; } int main() { int n, m, d; scanf("%d %d %d", &n, &m, &d); vector<forward_list<int> > ve (n, forward_list<int>()); for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); --a; --b; ve[a].push_front(b); ve[b].push_front(a); } unordered_set<int> ds; for (int i = 0; i < n; i++) { ds.insert (i); } for (int i = 0; i < ve.size(); ++i) { removeLessThanD(i, ve, d, ds); } unordered_set<int> notVisited (ds); if (notVisited.empty()) { printf("NIE"); } else { int maxVisitedCount = 0; forward_list<int> maxVisited; while (!notVisited.empty()) { int notVisitedSizeBefore = notVisited.size(); forward_list<int> visited; dfs(*notVisited.begin(), ve, notVisited, visited); int notVisitedSizeAfter = notVisited.size(); int visitedCount = notVisitedSizeBefore - notVisitedSizeAfter; if (visitedCount > maxVisitedCount) { maxVisitedCount = visitedCount; maxVisited = visited; } } maxVisited.sort(); printf("%d\n", maxVisitedCount); for (auto it = maxVisited.begin(); it != maxVisited.end(); ++it) { printf("%d ", (*it)+1); } } return 0; } |