Submission #180970

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

int N, G, E, p[101];
bool enemy[101];
bool used[101];
int dfs( vector< vector< pair< int, int > > >& edge , int idx, int& bit){
  if(used[idx]++) return 0;
  int ret = enemy[idx];
  for(int i = 0; i < edge[idx].size(); i++){
    if(bit >> edge[idx][i].second & 1) continue;
    ret += dfs( edge, edge[idx][i].first, bit);
  }
  return ret;
}

int main()
{
  cin >> N >> G >> E;


  for(int i = 0; i < G; i++){
    cin >> p[i];
    enemy[p[i]] = true;
  }
  vector < vector< pair< int, int > > > edge(N);

  for(int i = 0; i < E; i++){
    int a, b;
    cin >> a >> b;
    edge[a].push_back(make_pair(b, i));
    edge[b].push_back(make_pair(a, i));
  }
  if(E > 12) throw 0;
  int ret = 1 << 30;
  for(int i = 0; i < 1 << E; i++){
      fill_n( used, 100, false);
      ret = min( ret, __builtin_popcount(i) + dfs( edge, 0, i));
  }
  cout << ret << endl;
}

Submission Info

Judge Result