fork download
copy 
  1. #include <iostream>
  2. #include <set>
  3. #include <vector>
  4. #include <cassert>
  5. using namespace std;
  6.  
  7. const int nmax = 1e5 + 10;
  8.  
  9. set<int> forts;
  10. vector<int> g[nmax];
  11. vector<bool> mark;
  12. vector<pair<int, int> > frac;
  13.  
  14. bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
  15.     return (a.first * 1LL * b.second - a.second * 1LL * b.first < 0);
  16. }
  17.  
  18. void dfs(const int u) {
  19.     mark[u] = true;
  20.     for(int i = 0; i < g[u].size(); ++i) {
  21.         int v = g[u][i];
  22.         if(not mark[v]) dfs(v);
  23.         if(forts.count(v) == 0) frac[u].first++;
  24.         frac[u].second++;
  25.     }
  26. }
  27.  
  28. void dfs_runner(int n) {
  29.     mark.assign(n, false);
  30.     frac.reserve(n);
  31.     for(int i = 0; i < n; ++i) {
  32.         if(not mark[i]) {
  33.             dfs(i);
  34.         }
  35.     }
  36. }
  37.  
  38. struct cmpii {
  39.     bool operator()(const pair<pair<int, int>, int> &a, const pair<pair<int, int>, int> &b) const {
  40.         return cmp(a.first, b.first);
  41.     }
  42. };
  43.  
  44. int main() {
  45.     int n, m, k;
  46.     scanf("%d%d%d", &n, &m, &k);
  47.     for(int i = 0; i < k; ++i) {
  48.         int x; scanf("%d", &x);
  49.         x--;
  50.         forts.insert(x);
  51.     }
  52.     for(int i = 0; i < m; ++i) {
  53.         int a, b; scanf("%d%d", &a, &b);
  54.         a--; b--;
  55.         g[a].push_back(b);
  56.         g[b].push_back(a);
  57.     }
  58.     dfs_runner(n);
  59.  
  60.     multiset<pair<pair<int, int>, int>, cmpii> q;
  61.     vector<pair<pair<int, int>, int> > possibles;
  62.     for(int i = 0; i < n; ++i) {
  63.         if(forts.count(i) == 0) {
  64.             q.insert(make_pair(frac[i], i));
  65.         } else {
  66.             mark[i] = false;
  67.         }
  68.     }
  69.     while(not q.empty()) {
  70.         auto iii = *q.begin(); q.erase(q.begin());
  71.         possibles.push_back(iii);
  72.         int u = iii.second;
  73.         mark[u] = false;
  74.  
  75.         for(int i = 0; i < g[u].size(); ++i) {
  76.             int v = g[u][i];
  77.             if(mark[v]) {
  78.                 q.erase(q.find(make_pair(frac[v], v)));
  79.                 assert(frac[v].first >= 1);
  80.                 frac[v].first--;
  81.                 q.insert(make_pair(frac[v], v));
  82.             }
  83.         }
  84.     }
  85.  
  86.     int minidx = 0;
  87.     for(int i = 0; i < possibles.size(); ++i) {
  88.         auto kkk = possibles[minidx];
  89.         auto iii = possibles[i];
  90.         if(cmp(kkk.first, iii.first)) minidx = i;
  91.     }
  92.     printf("%d\n", (int)(possibles.size()) - minidx);
  93.     for(int i = minidx; i < possibles.size(); ++i) {
  94.         printf("%d ", possibles[i].second + 1);
  95.     }
  96.     return 0;
  97. }
  98.  
Success #stdin #stdout 0s 4640KB
comments (?)
stdin
copy 
9 8 4
3 9 6 8
1 2
1 3
1 4
1 5
2 6
2 7
2 8
2 9
stdout
copy 
3
1 4 5
https://ideone.com/INKqhS
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!