当前位置: 代码迷 >> 综合 >> A1134 Vertex Cover
  详细解决方案

A1134 Vertex Cover

热度:5   发布时间:2024-02-10 17:13:38.0

在这里插入图片描述
这个题写了这么久我是没想到的,原本就想建立一个二维数组,然后统计数边的个数,但是复杂度达到了n的3次方,内存超限,看了解析,直接给每个边命名,然后11条边11个名字,两个订单共享一个名字,然后最后遍历就行了。

#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<set>
#include<queue>
#include<unordered_set>
using namespace std;
int hashtable[10001];
vector<int>v[10001];
int main()
{int n, m, k, q; int temp1, temp2,cnt;cin >> n >> m;for (int i = 0; i < m; i++){cin >> temp1 >> temp2;v[temp1].push_back(i);v[temp2].push_back(i);}cin >> q;for (int i = 0; i <q; i++){cin >> k; memset(hashtable, 0, sizeof(hashtable));for (int j = 0; j < k; j++){cin >> temp2;for (int f = 0; f < v[temp2].size(); f++){hashtable[v[temp2][f]] = 1;}}int g; bool flag = false;for (g = 0; g <m; g++){if (hashtable[g] == 0){cout << "No" << endl;flag = true;break;}}if(flag==false)cout << "Yes" << endl;}
}