[PAT][Basic Level]1090

KEYWORDS: std :: map <int ,vector > mymap ;(图，构造int型 和 int型一维数组的映射，一 对 多)
mymap[item1].push_back(item2);
std::vector V; std::vector::iterator ;vector.begin();vector.end();
for(iterator = vector.begin() ; iterator != vector; iterator ++)

AC CODE:

#include <iostream>
#include <vector>
#include <map>
#define MAXN 100000
using namespace std;
int main()
{
    freopen("sample_input.txt","r",stdin);int N,K;map<int,vector<int> >m;cin>>N>>K;int item1,item2;for(int i = 0 ; i < N ; i ++){
    scanf("%d%d",&item1,&item2);m[item1].push_back(item2);m[item2].push_back(item1);}while(K--){
    int total;bool flag[MAXN] = {
    false};bool flag_is_safe = true;scanf("%d",&total);vector<int> v(total);for(int i = 0 ; i < total ; i ++){
    scanf("%d",&v[i]);flag[v[i]] = true;}vector<int> ::iterator it;for( it = v.begin() ; it != v.end() ; it ++){
    //cout<<*it<<endl;//cout<<m[*it]<<endl;for(int j =0 ; j < m[*it].size() ; j ++)if(flag[m[*it][j]]){
    flag_is_safe = false;}}if(flag_is_safe) printf("Yes\n");else printf("No\n");}
}

Aside Note:如果题目没有对顺序有明确的要求，使用unordered_map比map效率更快。C++ reference 中在

• map containers are generally slower than unordered_map containers to
  access individual elements by their key, but they allow the direct
  iteration on subsets based on their order.

Code of Problem1090(used unordered_map header):

#include <iostream>
#include <vector>
#include <unordered_map>
#define MAXN 100000
using namespace std;
int main()
{
    freopen("sample_input.txt","r",stdin);int N,K;unordered_map<int,vector<int> >m;cin>>N>>K;int item1,item2;for(int i = 0 ; i < N ; i ++){
    scanf("%d%d",&item1,&item2);m[item1].push_back(item2);m[item2].push_back(item1);}while(K--){
    int total;bool flag[MAXN] = {
    false};bool flag_is_safe = true;scanf("%d",&total);vector<int> v(total);for(int i = 0 ; i < total ; i ++){
    scanf("%d",&v[i]);flag[v[i]] = true;}vector<int> ::iterator it;for( it = v.begin() ; it != v.end() ; it ++){
    //cout<<*it<<endl;//cout<<m[*it]<<endl;for(int j =0 ; j < m[*it].size() ; j ++)if(flag[m[*it][j]]){
    flag_is_safe = false;}}if(flag_is_safe) printf("Yes\n");else printf("No\n");}
}