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.
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.
For each of the M queries, print in a line
Yesif the given subset of vertices can form a maximal clique; or if it is a clique but not a maximal clique, printNot Maximal; or if it is not a clique at all, printNot a Clique.
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
Yes Yes Yes Yes Not Maximal Not a Clique
1 /* 2 Data: 2019-05-23 20:57:23 3 Problem: PAT_A1142#Maximal Clique 4 AC: 49:30 5 6 题目大意： 7 判断所给子图是否是完全图 8 输入： 9 第一行给出，顶点数Nv<=200，Ne边数 10 接下来Ne行，给出边的头尾结点 11 接下来一行，给出查询数M； 12 接下来M行，给出顶点数K，和K个顶点； 13 */ 14 15 #include<cstdio> 16 #include<algorithm> 17 const int M=210; 18 int grap[M][M],vis[M]; 19 20 int main() 21 { 22 #ifdef ONLINE_JUDGE 23 #else 24 freopen("Test.txt", "r", stdin); 25 #endif 26 27 int n,m,q,v1,v2,v[M]; 28 scanf("%d%d", &n,&m); 29 std::fill(grap[0],grap[0]+M*M,0); 30 for(int i=0; i<m; i++) 31 { 32 scanf("%d%d", &v1,&v2); 33 grap[v1][v2]=1; 34 grap[v2][v1]=1; 35 } 36 scanf("%d", &m); 37 for(int i=0; i<m; i++) 38 { 39 scanf("%d", &q); 40 std::fill(vis,vis+n+1,0); 41 for(int j=0; j<q; j++) 42 { 43 scanf("%d", &v[j]); 44 vis[v[j]]=1; 45 } 46 for(int j=0; j<q; j++) 47 { 48 v1=v[j]; 49 for(int k=0; k<q; k++) 50 { 51 v2=v[k]; 52 if(k==j) continue; 53 if(grap[v1][v2]==0) 54 { 55 vis[0]=1;break; 56 } 57 } 58 if(vis[0]==1) break; 59 } 60 if(vis[0]==1) 61 printf("Not a Clique\n"); 62 else 63 { 64 for(v1=1; v1<=n; v1++) 65 { 66 if(vis[v1]==1) continue; 67 vis[0]=0; 68 for(int k=0; k<q; k++) 69 { 70 v2=v[k]; 71 if(grap[v1][v2]==1) 72 vis[0]++; 73 } 74 if(vis[0]==q) 75 break; 76 } 77 if(vis[0]==q) 78 printf("Not Maximal\n"); 79 else 80 printf("Yes\n"); 81 } 82 } 83 84 return 0; 85 }
原文：https://www.cnblogs.com/blue-lin/p/10915194.html