题目

题目大意

给定一个图，n是定点数，m是边数，给出每条边的两个顶点来表示边。又给定k个顶点集，要求判断这些顶点集是否是定点覆盖集。是的话输出Yes，否则输出No。

思路

vertex cover是顶点覆盖的意思，即该定点集中的所有顶点能够覆盖图中的所有边。因为要根据顶点找到与之关联的所有边，所以图可以用二维数组来存储，定点为键，其值是一个数组，存放与该定点关联的边，运用了哈希的思想。可以用布尔数组表示每条边是否被访问，如果全部被访问，就说明是顶点覆盖，否则就不是。

代码

#include <iostream>
#include <vector>
using namespace std;int main(){int n, m, k;cin >> n >> m;vector<int> v[n];for (int i = 0; i < m; i++){int v1, v2;cin >> v1 >> v2;v[v1].push_back(i);v[v2].push_back(i);}  // 记录每个顶点所连接的边，以顶点为键，边为值，哈希思想cin >> k;for (int t = 0; t < k; t++){int num;cin >> num;vector<bool> b(m);  // 每条边是否都被记录for (int i = 0; i < num; i++){int vi;cin >> vi;for (int j = 0; j < (int)v[vi].size(); j++){b[v[vi][j]] = true;}}int flag = 0;for (int i = 0; i < m; i++){if (b[i] == false){flag = 1;}}if (flag == 0){cout << "Yes" << endl;}else{cout << "No" << endl;}}return 0;
}
/*
vertex cover是顶点覆盖，就是 顶点集 中的所有顶点能连接所有的边，即覆盖整个图。
*/