您好,欢迎来到尚车旅游网。
搜索
您的当前位置:首页PAT【甲级】1142

PAT【甲级】1142

来源:尚车旅游网

题目链接:
题目简述:这个题目还是依旧给个图。在题目中给了一个名为clique的定义,即:它为所给图所有节点的子集,且在这个集合中的节点两两邻接。如果再加入其它的节点还满足两两相连,那么这个clique就是Not Maximal,否则就是Yes

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> graph(201, vector<int>(201, 0));
vector<int> adj[201], temp(201);

void getAns(int k){
    for (int i = 0; i < k;i++){
        for (int j = i + 1; j < k;j++){
            if(graph[temp[i]][temp[j]] == 0){
                cout << "Not a Clique" << endl;
                return;
            }
        }
    }
    for (int i = 0; i < k;i++){
        for (int j = 0; j < adj[temp[i]].size();j++){
            int h = 0;
            for (; h < k;h++){
                if(h == i) continue;
                if(graph[temp[h]][adj[temp[i]][j]] == 0)
                    break;
            }
            if(h == k){
                cout << "Not Maximal" << endl;
                return;
            }
        }
    }
    cout << "Yes" << endl;
    return;
}

int main(){
    int N, E, M, K;
    int c1, c2;
    cin >> N >> E;
    for (int i = 0; i < E;i++){
        cin >> c1 >> c2;
        graph[c1][c2] = graph[c2][c1] = 1;
        adj[c1].push_back(c2);
        adj[c2].push_back(c1);
    }
    cin >> M;
    while(M--){
        cin >> K;
        for (int i = 0; i < K;i++)
            cin >> temp[i];
        getAns(K);
    }
    return 0;
}

就是先按平常的先把图存起来,然后再去判断。这边判断就是纯暴力了,直接一遍撸过去,不过得先判是不是团,再判是不是不是最大团,最后再输出最大团return的逻辑还是很好用的

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- sceh.cn 版权所有 湘ICP备2023017654号-4

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务