// Potyczki Algorytmiczne 2015 // runda 2 // MIStrzostwa // Tomasz Pastusiak #include <iostream> #include <algorithm> #include <functional> #include <stack> #include <set> #include <vector> using namespace std; #define MAX_M_N 200001 int connectionLevel[MAX_M_N]; // 1 .. n bool badCityNoticed[MAX_M_N]; // 1 .. n stack<int> badCities; // this could be a stack vector<int> g[MAX_M_N]; int groupNumber[MAX_M_N]; int groupSizes[MAX_M_N]; int main(){ ios_base::sync_with_stdio(false); int n,m,d,a,b; cin >> n >> m >> d; for(int i=1 ;i<=n; ++i){ connectionLevel[i] = 0; badCityNoticed[i] = false; groupNumber[i] = -1; groupSizes[i] = 0; } for(int i=0; i<m; ++i){ cin >> a >> b; ++connectionLevel[a]; ++connectionLevel[b]; g[a].push_back(b); g[b].push_back(a); } /*for(int i=1; i<=n ; ++i){ cout << "City " << i << " lev: " << connectionLevel[i] << " noticed: " << badCityNoticed[i] << " good: " << (connectionLevel[i] >= d ? 'Y' : 'N') << endl; }*/ // now we know which cities are good, just check connectionLevel[city] >= d for(int i=1 ;i<=n; ++i){ if(connectionLevel[i] < d){ badCities.push(i); badCityNoticed[i] = true; } } /*cout << "---------" << endl; for(int i=1; i<=n ; ++i){ cout << "City " << i << " lev: " << connectionLevel[i] << " noticed: " << badCityNoticed[i] << " good: " << (connectionLevel[i] >= d ? 'Y' : 'N') << endl; }*/ while(!badCities.empty()){ int badass = badCities.top(); badCities.pop(); for(int i=0; i<g[badass].size(); ++i){ int otherCity = g[badass][i]; --connectionLevel[ otherCity ]; if(connectionLevel[ otherCity ] < d && badCityNoticed[otherCity] == false){ badCities.push(otherCity); badCityNoticed[otherCity] = true; } } // for each friend of bad city } /*cout << "---------" << endl; for(int i=1; i<=n ; ++i){ cout << "City " << i << " lev: " << connectionLevel[i] << " noticed: " << badCityNoticed[i] << " good: " << (connectionLevel[i] >= d ? 'Y' : 'N') << endl; }*/ // now we have to do DFS (BFS) to count sizes of groups stack<int> searchStack; for(int i=1 ;i<=n; ++i){ if(groupNumber[i] == -1){ groupNumber[i] = i; if(badCityNoticed[i]) continue; searchStack.push(i); while(!searchStack.empty()){ int v = searchStack.top(); searchStack.pop(); for(int j=0; j<g[v].size(); ++j){ int otherCity = g[v][j]; if(badCityNoticed[otherCity] == false && groupNumber[otherCity] == -1){ groupNumber[otherCity] = groupNumber[v]; searchStack.push(otherCity); } // if friend is also good and unvisited, add it to group } // for each friend of good city } } // if doesn't belong to any group } for(int i=1 ;i<=n; ++i){ ++groupSizes[ groupNumber[i] ]; } int biggestGroup = 1; for(int i=1 ;i<=n; ++i){ if(groupSizes[i] > groupSizes[biggestGroup]) biggestGroup = i; } if( badCityNoticed[biggestGroup] ){ cout << "NIE" << endl; } else{ cout << groupSizes[biggestGroup] << endl; for(int i=1 ;i<=n; ++i){ if(groupNumber[i] == biggestGroup) cout << i << ' '; } 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 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 | // Potyczki Algorytmiczne 2015 // runda 2 // MIStrzostwa // Tomasz Pastusiak #include <iostream> #include <algorithm> #include <functional> #include <stack> #include <set> #include <vector> using namespace std; #define MAX_M_N 200001 int connectionLevel[MAX_M_N]; // 1 .. n bool badCityNoticed[MAX_M_N]; // 1 .. n stack<int> badCities; // this could be a stack vector<int> g[MAX_M_N]; int groupNumber[MAX_M_N]; int groupSizes[MAX_M_N]; int main(){ ios_base::sync_with_stdio(false); int n,m,d,a,b; cin >> n >> m >> d; for(int i=1 ;i<=n; ++i){ connectionLevel[i] = 0; badCityNoticed[i] = false; groupNumber[i] = -1; groupSizes[i] = 0; } for(int i=0; i<m; ++i){ cin >> a >> b; ++connectionLevel[a]; ++connectionLevel[b]; g[a].push_back(b); g[b].push_back(a); } /*for(int i=1; i<=n ; ++i){ cout << "City " << i << " lev: " << connectionLevel[i] << " noticed: " << badCityNoticed[i] << " good: " << (connectionLevel[i] >= d ? 'Y' : 'N') << endl; }*/ // now we know which cities are good, just check connectionLevel[city] >= d for(int i=1 ;i<=n; ++i){ if(connectionLevel[i] < d){ badCities.push(i); badCityNoticed[i] = true; } } /*cout << "---------" << endl; for(int i=1; i<=n ; ++i){ cout << "City " << i << " lev: " << connectionLevel[i] << " noticed: " << badCityNoticed[i] << " good: " << (connectionLevel[i] >= d ? 'Y' : 'N') << endl; }*/ while(!badCities.empty()){ int badass = badCities.top(); badCities.pop(); for(int i=0; i<g[badass].size(); ++i){ int otherCity = g[badass][i]; --connectionLevel[ otherCity ]; if(connectionLevel[ otherCity ] < d && badCityNoticed[otherCity] == false){ badCities.push(otherCity); badCityNoticed[otherCity] = true; } } // for each friend of bad city } /*cout << "---------" << endl; for(int i=1; i<=n ; ++i){ cout << "City " << i << " lev: " << connectionLevel[i] << " noticed: " << badCityNoticed[i] << " good: " << (connectionLevel[i] >= d ? 'Y' : 'N') << endl; }*/ // now we have to do DFS (BFS) to count sizes of groups stack<int> searchStack; for(int i=1 ;i<=n; ++i){ if(groupNumber[i] == -1){ groupNumber[i] = i; if(badCityNoticed[i]) continue; searchStack.push(i); while(!searchStack.empty()){ int v = searchStack.top(); searchStack.pop(); for(int j=0; j<g[v].size(); ++j){ int otherCity = g[v][j]; if(badCityNoticed[otherCity] == false && groupNumber[otherCity] == -1){ groupNumber[otherCity] = groupNumber[v]; searchStack.push(otherCity); } // if friend is also good and unvisited, add it to group } // for each friend of good city } } // if doesn't belong to any group } for(int i=1 ;i<=n; ++i){ ++groupSizes[ groupNumber[i] ]; } int biggestGroup = 1; for(int i=1 ;i<=n; ++i){ if(groupSizes[i] > groupSizes[biggestGroup]) biggestGroup = i; } if( badCityNoticed[biggestGroup] ){ cout << "NIE" << endl; } else{ cout << groupSizes[biggestGroup] << endl; for(int i=1 ;i<=n; ++i){ if(groupNumber[i] == biggestGroup) cout << i << ' '; } cout << endl; } return 0; } |