【PTA Advanced】1142 Maximal Clique（C++）

目录

题目

Input Specification:

Output Specification:

Sample Input:

Sample Output:

思路

代码

---

题目

A clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. A maximal clique is a clique that cannot be extended by including one more adjacent vertex. (Quoted from https://en.wikipedia.org/wiki/Clique_(graph_theory))

Now it is your job to judge if a given subset of vertices can form a maximal clique.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers Nv (≤ 200), the number of vertices in the graph, and Ne, the number of undirected edges. Then Ne lines follow, each gives a pair of vertices of an edge. The vertices are numbered from 1 to Nv.

After the graph, there is another positive integer M (≤ 100). Then M lines of query follow, each first gives a positive number K (≤ Nv), then followed by a sequence of K distinct vertices. All the numbers in a line are separated by a space.

Output Specification:

For each of the M queries, print in a line Yes if the given subset of vertices can form a maximal clique; or if it is a clique but not a maximal clique, print Not Maximal; or if it is not a clique at all, print Not a Clique.

Sample Input:

8 10
5 6
7 8
6 4
3 6
4 5
2 3
8 2
2 7
5 3
3 4
6
4 5 4 3 6
3 2 8 7
2 2 3
1 1
3 4 3 6
3 3 2 1

Sample Output:

Yes
Yes
Yes
Yes
Not Maximal
Not a Clique

思路

难度评级：⭐️

代码

#include <iostream>
#include <vector>
#include <set>using namespace std;int matrix[201][201]={0};// 邻接矩阵 int main(int argc, char** argv) {int nv,ne;cin>>nv>>ne;for(int i=0;i<ne;i++) {int a,b;cin>>a>>b;matrix[a][b]=matrix[b][a]=1;}int m;cin>>m;for(int i=0;i<m;i++) {int k;cin>>k;// 输入clique set<int> cliqueSet;vector<int> cliqueVec;for(int j=0;j<k;j++) {int v;cin>>v;cliqueVec.push_back(v);cliqueSet.insert(v);}// 判断clique内的每个顶点之间是否相邻bool isClique=true; for(int j=0;j<k-1;j++) {for(int m=j+1;m<k;m++) {if(matrix[cliqueVec[j]][cliqueVec[m]]==0) {isClique=false;break;	}}if(!isClique) break;} if(!isClique) {cout<<"Not a Clique"<<endl;continue;}// 判断是否还可以添加另外的顶点bool isMax=true;for(int j=1;j<=nv;j++) {if(cliqueSet.count(j)==0) {int m;for(m=0;m<k;m++) {if(matrix[j][cliqueVec[m]]==0) break;}if(m>=k) {isMax=false;break;}}} if(!isMax) cout<<"Not Maximal"<<endl;else cout<<"Yes"<<endl;} return 0;
}