19. （完善程序）

（最小垄断集）问题：你有一张 n 个结点（结点编号从 1 到 n），m 条边的无向无权图 G=(V,E)，其中 V 为点集，E 为边集。称 V 的一个子集 S 垄断了图 G，当且仅当 ∀(u,v) ∈ E，u,v 中必然恰有一个结点在 S 内。求垄断了 G 的子集 S 至少有多少个元素，或报告不存在这样的子集。试补全程序。

#include<bits/stdc++.h>
using namespace std;
int n,m,is[100005];
vector<int> g[100005];
queue<int> q;
int main(){
  cin>>n>>m;
  for(int i=1;i<=m;i++){
    int u,v;
    cin>>u>>v;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }
  int tot=0;
  for(int k=1;k<=n;k++){
    if(_________________________) continue;
    q.emplace(k);
    is[k]=1;
    int cnt[3]=_________________________;
    while(q.size()){
      for(int i=0;i<g[q.front()].size();i++){
        int to=g[q.front()][i];
        if(is[to]==0){
          is[to]=_________________________;
          cnt[is[to]]++;
          q.emplace(to);
        } else if(_________________________){
          puts("No such subset."); //报告不存在这样的子集
          return 0;
        }
      }
      q.pop();
    }
    tot+=_________________________;
  }
  cout<<tot;
  return 0;
}

① 处应填（ ）。

{{ select(1) }}

• is[k]
• is[k]==0
• q.empty()
• tot>k

② 处应填（ ）。

{{ select(2) }}

• {0,0,0}
• {0,0,1}
• {1,0,0}
• {0,1,0}

③ 处应填（ ）。

{{ select(3) }}

• is[q.front()]
• 3-is[q.front()]
• !is[q.front()]
• q.front()

④ 处应填（ ）。

{{ select(4) }}

• is[to]==is[q.front()]
• is[to]!=is[q.front()]
• is[to]&&is[q.front()]
• abs(is[to]-is[q.front()])==1

⑤ 处应填（ ）。

{{ select(5) }}

• cnt[1]
• min(cnt[0],cnt[1])
• min(cnt[1],cnt[2])
• cnt[1]+cnt[2]