問題概要
解法
最初に判定問題を考える． \(1, \cdots , k\) 以外の頂点を全て消したとき，接続されていることが必要十分． これは， \(k\) について昇順に頂点を追加していき，小さい番号に向かう辺だけ追加すれば， 頂点 \(1, \cdots, k\) からなる fullsubgraph が作れる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,m;
cin >> n >> m;
UnionFind<ll> uf(n);
vvll to(n);
rep(i,m){
ll a,b; cin >> a >> b;
--a, --b;
to[a].emplace_back(b);
to[b].emplace_back(a);
}
rep(cu,n){
for(auto ne: to[cu]){
if(cu > ne) {
uf.merge(cu,ne); // 判定
}
if(cu < ne){
if(connected[ne]) continue;
connected[ne] = true;
cc_vx_cnt++;
}
}
if(connected[cu]) cc_vx_cnt--;
ll ans;
if(uf.size(cu) != cu + 1){ // 判定
ans = -1;
}else{
ans = cc_vx_cnt;
}
cout << ans << "\n";
}
return 0;
}
