fork download
copy 
  1. #include <bits/stdc++.h>
  2. //#include <ext/pb_ds/assoc_container.hpp> // Common file
  3. //#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
  4.  
  5. using namespace std;
  6. //using namespace __gnu_pbds;
  7. //typedef tree< pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>
  8. //ordered_set;
  9. int dx[] = {0, 1, 0, -1};
  10. int dy[] = {-1, 0, 1, 0};
  11. #define X first
  12. #define Y second
  13. #define int long long int 
  14. const int N = (int)2e5 + 10;
  15. const int MOD = 1000000007;
  16.  
  17. int n, m, x;
  18. vector<vector<int>> g;
  19. vector<int> inf;
  20. int rem; int in;
  21. vector<bool> vis;
  22.  
  23. void dfs(int u){
  24.     in++;
  25.     vis[u] = true;
  26.     for(auto & x: g[u]){
  27.         if(x == rem) continue;
  28.         if(!vis[x])
  29.             dfs(x);
  30.     }
  31. }
  32.  
  33. void solve(){
  34.     cin >> n >> m >> x;
  35.     g = vector<vector<int>>(n + 1, vector<int>());
  36.     inf = vector<int>(x);
  37.     for(int i = 0; i < x; ++i)
  38.         cin >> inf[i];
  39.     for(int i = 0, x, y; i < m; ++i){
  40.         cin >> x >> y;
  41.         g[x].emplace_back(y);
  42.         g[y].emplace_back(x);
  43.     }
  44.     //start by removing every node
  45.     sort(inf.begin(), inf.end());
  46.     int mx = 0;
  47.     int id = 0;
  48.     vis = vector<bool>(n + 1, false);
  49.     for(int i = 0; i < x; ++i){
  50.         in = 1;
  51.         rem = inf[i];
  52.         fill(vis.begin(), vis.end(), false);
  53.         for(int j = 0; j < x; ++j){
  54.             if(j == i) continue;
  55.             if(!vis[inf[j]]){
  56.                 dfs(inf[j]);
  57.             }
  58.         }
  59.         int ans = n - in;
  60.         if( ans > mx){
  61.             mx = ans;
  62.             id = inf[i];
  63.         }
  64.     }
  65.     cout << mx << " " << id << '\n';
  66.  
  67. }   
  68.  
  69. int32_t main(){
  70.     ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); 
  71.     int t; cin >> t;
  72.     while(t--)
  73.         solve();
  74.     return 0;
  75. }
Success #stdin #stdout 0s 4548KB
comments (?)
stdin
copy 
3
4 4 1
3
1 2
1 3
2 3
3 4
4 4 2
3 4
1 2
1 3
2 3
3 4
3 2 1
2
1 2
2 3
stdout
copy 
3 3
2 3
2 2
https://ideone.com/EzR8Xz
language:
C++14 (gcc 8.3)
created:
4 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!