A1134.md

A1134 Vertex Cover

1.题意理解

给出vertex cover的定义：一个图的vertex的子集，所有边至少和其中一个结点有关。

2.思路分析

hash思想，每读入一个结点，就把它连接的边标记上，最后检查所有边是否都被标记即可

3.参考代码

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

const int N = 10010;
vector<int> adj[N];

int main()
{
    int n, m, k, u, v, nv;

    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    scanf("%d", &k);
    for (int i = 0; i < k; i++)
    {
        bool flag = true;
        vector<int> degree(n);
        for (int j = 0; j < n; j++)
            degree[j] = adj[j].size();

        scanf("%d", &nv);
        for (int j = 0; j < nv; j++)
        {
            scanf("%d", &u);
            degree[u] = 0;

            for (int v : adj[u])
                if (degree[v])
                    degree[v]--;
        }

        for (int it : degree)
        {
            if (it)
            {
                flag = false;
                break;
            }
        }

        printf("%s\n", flag ? "Yes" : "No");
    }

    return 0;
}