Topic: Give a graph and K queries, each query gives Nv nodes, and ask if the edges associated with these nodes contain all the edges of the whole graph.
Ideas: Firstly, because of the large number of nodes, adjacency table is used to store the graph, and unordered_map< int, unordered_map< int, bool> & gt; MP is used to represent the adjacency relationship between two vertices. When you query, read every time.If the number of edges deleted is equal to the total number of edges of the graph, output Yes; otherwise output No. PS. actually needs no additional vector< int> Adj[] storage diagram, because unordered_Map<, int, unordered_map< int, bool> > MP can represent a graph.
Code:
#include <cstdio> #include <vector> #include <unordered_map> using namespace std; const int maxn=10005; vector<int> Adj[maxn]; int main() { int n,m; scanf("%d%d",&n,&m); unordered_map<int,unordered_map<int,bool>> mp,tmpMp; int u,v; for(int i=0;i<m;i++){ scanf("%d%d",&u,&v); Adj[u].push_back(v); Adj[v].push_back(u); mp[u][v]=mp[v][u]=true; } int k,queryCnt; scanf("%d",&queryCnt); for(int i=0;i<queryCnt;i++){ scanf("%d",&k); tmpMp=mp; int cnt=0;//Indicates the number of edges deleted. for(int j=0;j<k;j++){ scanf("%d",&v); for(int i=0;i<Adj[v].size();i++){//Delete the adjacent edge of node V int u=Adj[v][i]; if(tmpMp[v][u]==true){ cnt++; tmpMp[v][u]=tmpMp[u][v]=false; } } } if(cnt==m) printf("Yes\n"); else printf("No\n"); } return 0; }