题意:给出一个图和k个查询,每个查询给出Nv个结点,问与这些结点相关的边是否包含了整个图的所有边。
思路:首先,因为结点数较多,用邻接表存储图,并用unordered_map<int,unordered_map<int,bool>> mp;表示两个顶点的相邻关系。查询时,每读入一个结点,就删除与该结点相邻的所有邻边,若最后删除的边数恰等于图的总边数,输出Yes;否则输出No。ps.其实无需额外用vector<int> Adj[]存储图,因为unordered_map<int,unordered_map<int,bool>> mp就可以表示一个图了。
代码:
#include#include #include using namespace std;const int maxn=10005;vector Adj[maxn];int main(){ int n,m; scanf("%d%d",&n,&m); unordered_map > mp,tmpMp; int u,v; for(int i=0;i