- Quiz
- AC
- 解説
- 辺でunion findしていく
- governmentのいる連結成分ごとに、全点間で辺をはる
- governmentのいない街をすべて集めて、全点間で辺をはる★
- 最後に★から最大サイズの(governmentのある)街に、全点間で辺をはる
- これで最大本数の辺がはれる
#include <atcoder/dsu>
using namespace atcoder;
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
ll N,M,K;
cin>>N>>M>>K;
set<ll> se;
rep(i,K){
ll a;cin>>a;a--;
se.insert(a);
}
dsu uf(N);
VI A,B;
rep(i,M){
ll a,b;cin>>a>>b;a--;b--;
A.push_back(a);
B.push_back(b);
uf.merge(a,b);
}
auto groups = uf.groups();
map<ll,ll> mp;
rep(i,M){
ll a = A[i];
ll r = uf.leader(a);
mp[r]++;
}
ll ans=0;
ll max_government_size = 0;
ll government_edge_cnt = 0;
ll government_city_cnt = 0;
for(auto group : groups){
bool is_government=false;
for(int i : group){
if(se.count(i))is_government=true;
}
if(is_government){
ll r = uf.leader(group[0]);
ll edge_num = mp[r];
ll sz = group.size();
ll edge_max_num = sz*(sz-1)/2;
ans += edge_max_num - edge_num;
chmax(max_government_size, sz);
government_edge_cnt += edge_num;
government_city_cnt += sz;
}
}
ll non_government_city_num = N - government_city_cnt;
ll non_government_edge_num = M - government_edge_cnt;
ll max_edge = non_government_city_num * (non_government_city_num-1)/2;
ll add = max_edge - non_government_edge_num;
ans += add;
ans += max_government_size * non_government_city_num;
p(ans);
return 0;
}