文章目录
pat甲级 1134 Vertex Cover (25分)1.分析2.代码
pat甲级 1134 Vertex Cover (25分)
1.分析
note:只需要明白两点，(1)题目第一句话： A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. 什么意思。 （2）能否想到给边编号存储，不用邻接矩阵不用邻接表
这道题会就满分不会就零分。
2.代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std
;
vector
<bool> visit
;
vector
<vector
<int>> edge
;
int main()
{
int n
,m
,k
,a
,b
,nv
;
cin
>>n
>>m
;
edge
.resize(n
);
visit
.resize(m
);
for(int i
=0;i
<m
;++i
)
{
cin
>>a
>>b
;
edge
[a
].push_back(i
);
edge
[b
].push_back(i
);
}
cin
>>k
;
while(k
--)
{
cin
>>nv
;
fill(visit
.begin(),visit
.end(),true);
bool flag
=true;
while(nv
--)
{
cin
>>a
;
for(auto i
:edge
[a
]) visit
[i
]=false;
}
for(auto i
:visit
) if(i
) {flag
=false;break;}
printf("%s\n",flag
?"Yes":"No");
}
return 0;
}
