开发者社区云计算文章正文

1142. Maximal Clique (25) 19‘

2018-03-18 982

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： #include #include #include #include #include using namespace std;int e[201][201];vector temp;bool judge(){ int flag = 1; for(int i = 0; i < temp.

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int e[201][201];
vector<int> temp;

bool judge(){
    int flag = 1;
    for(int i = 0; i < temp.size(); i++){
        for(int j = i + 1; j < temp.size(); j++){
            if(!e[temp[i]][temp[j]]){
                flag = 0;
                break;
            }
        }
    }
    return flag;
}

int main( )
{
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        e[a][b] = e[b][a] = 1;
    }


    int k;
    cin >> k;
    for(int i = 0; i < k; i++){
        int c;
        cin >> c;
        temp.clear();
        vector<bool> book(n+1);
        for(int j = 0; j < c; j++){
            int t;
            cin >> t;
            book[t] = true;
            temp.push_back(t);
        }
        int flag = 1;
        if(c == 1){ printf("Yes\n"); continue;}
        if(judge()){
            for(int i = 1; i <= n; i++){
                if(!book[i]){
                    temp.push_back(i);
                    if(judge()){
                        flag = 0;
                        break;
                    }
                    temp.pop_back();
                }
            }
            if(flag){
                printf("Yes\n");
            }else{
                printf("Not Maximal\n");
            }
        }else{
            printf("Not a Clique\n");
        }

    }

    return 0;
}