关于算法-数据结构:PAT甲级1142-Maximal-Clique

题目粗心：

给定一个无向图 G，顶点编号为 1 到 Nv,Ne 条边，判断给出的一组顶点汇合是否形成该图的一个极大齐全子图，如果是输入 Yes, 否则判断是否是一个齐全子图，如果是输入 Not Maximal，否则输入 Not a Clique。

算法思路：

首先得判断输出的汇合是否是以后图 G 的一个齐全子图，这里采纳 isClique 函数来实现，如果是就再判断是否是一个极大齐全子图，这里采纳 isMaximal 来实现，最初就依据判断的后果进行相应的输入就好。

isClique 函数：

间接遍历输出汇合的不同顶点之间是否存在不邻接的点，如果是就返回 false，否则返回 true。

bool G[201][201];// 邻接矩阵，判断 2 点是否邻接 
bool isClique(const vector<int> &a){for(int i:a){for(int j:a){if(i!=j&&!G[i][j]){
                // 存在不邻接的结点 
                return false;
            }
        }
    }
    return true;
}

isMaximal 函数：

咱们应用 exist 标记所有输出的结点，而后遍历所有的顶点，只有没有呈现在输出汇合中并且与汇合所有顶点都邻接，阐明不是极大齐全子图，返回 false, 否则返回 true。

bool G[201][201];// 邻接矩阵，判断 2 点是否邻接 
bool exist[201];// 标记每一个在 subset 中的结点编号 
bool isMaximal(const vector<int> &a,int N){for(int i=1;i<=N;++i){if(exist[i]) continue;
        bool isAllAdjcent = true;
        for(int j:a){
            // 得判断 i 和所有的点是否邻接
            if(!G[i][j]){
                isAllAdjcent = false;
                break;
            }
        }
        if(isAllAdjcent){
            // 能够扩大一个邻接点 
            return false;
        }
    }
    return true;
}

提交后果：

AC 代码：

#include<cstdio>
#include<vector>
#include<cstring>

using namespace std;

bool G[201][201];// 邻接矩阵，判断 2 点是否邻接 
bool exist[201];// 标记每一个在 subset 中的结点编号 
 
bool isClique(const vector<int> &a){for(int i:a){for(int j:a){if(i!=j&&!G[i][j]){
                // 存在不邻接的结点 
                return false;
            }
        }
    }
    return true;
}

bool isMaximal(const vector<int> &a,int N){for(int i=1;i<=N;++i){if(exist[i]) continue;
        bool isAllAdjcent = true;
        for(int j:a){
            // 得判断 i 和所有的点是否邻接
            if(!G[i][j]){
                isAllAdjcent = false;
                break;
            }
        }
        if(isAllAdjcent){
            // 能够扩大一个邻接点 
            return false;
        }
    }
    return true;
}

int main(){
    int Nv,Ne;
    scanf("%d %d",&Nv,&Ne);
    int a,b;
    for(int i=0;i<Ne;++i){scanf("%d %d",&a,&b);
        G[a][b] = G[b][a] = true;
    }
    int M,N;
    scanf("%d",&M);
    for(int i=0;i<M;++i){
        vector<int> subset;
        memset(exist,0,sizeof(exist));
        scanf("%d",&N);
        for(int j=0;j<N;++j){scanf("%d",&a);
            exist[a] = true;
            subset.push_back(a);
        }
        if(!isClique(subset)){printf("Not a Clique\n");
        }else if(!isMaximal(subset,Nv)) {printf("Not Maximal\n");
        }else {printf("Yes\n");
        }
    }
    return 0;
}