PAT_A1142#Maximal Clique

我会带着你远行 2021-12-20 06:29 99阅读 0赞

### Source: ###

> [PAT A1142 Maximal Clique (25 分)][PAT A1142_Maximal Clique_25]

### Description: ###

> 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][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

### Keys: ###

*  [图的存储和遍历][Link 1]

### Attention: ###

*  想的有点多，数据规模不大，暴力求解就好了

### Code: ###

1 /*
     2 Data: 2019-06-20 15:52:01
     3 Problem: PAT_A1142#Maximal Clique
     4 AC: 30：25
     5 
     6 题目大意：
     7 判断所给子图是否是完全图（无向图）
     8 输入：
     9 第一行给出，顶点数Nv<=200，Ne边数
    10 接下来Ne行，v1,v2
    11 接下来一行，给出查询数M；
    12 接下来M行，给出顶点数K，和K个顶点；
    13 输出：
    14 YES，最大完全子图；
    15 Not Maximal，完全子图，非最大
    16 Not a Clique，完全图
    17 
    18 基本思路：
    19 先判断所给子图是否是完全图，
    20 再遍历图中其余顶点，加入该子图，判断是否为完全图
    21 */
    22 #include<cstdio>
    23 #include<algorithm>
    24 using namespace std;
    25 const int M=210;
    26 int grap[M][M],ver[M],vis[M];
    27 
    28 int main()
    29 {
    30 #ifdef ONLINE_JUDGE
    31 #else
    32     freopen("Test.txt", "r", stdin);
    33 #endif // ONLINE_JUDGE
    34 
    35     fill(grap[0],grap[0]+M*M,0);
    36     int n,m,k,v1,v2;
    37     scanf("%d%d", &n,&m);
    38     for(int i=0; i<m; i++)
    39     {
    40         scanf("%d%d", &v1,&v2);
    41         grap[v1][v2]=1;
    42         grap[v2][v1]=1;
    43     }
    44     scanf("%d", &m);
    45     while(m--)
    46     {
    47         fill(vis,vis+M,0);
    48         scanf("%d", &k);
    49         for(int i=0; i<k; i++){
    50             scanf("%d", &ver[i]);
    51             vis[ver[i]]=1;
    52         }
    53         int ans=1;
    54         for(int i=0; i<k-1; i++){
    55             for(int j=i+1; j<k; j++)
    56                 if(grap[ver[i]][ver[j]]==0){
    57                     ans=0;break;
    58                 }
    59             if(ans==0)
    60                 break;
    61         }
    62         if(ans==0)
    63             printf("Not a Clique\n");
    64         else
    65         {
    66             for(int i=1; i<=n; i++){
    67                 if(vis[i]==1)
    68                     continue;
    69                 ans=0;
    70                 for(int j=0; j<k; j++){
    71                     if(grap[i][ver[j]]==0){
    72                         ans=1;break;
    73                     }
    74                 }
    75                 if(ans==0){
    76                     printf("Not Maximal\n");
    77                     break;
    78                 }
    79             }
    80             if(ans==1)
    81                 printf("Yes\n");
    82         }
    83     }
    84 
    85     return 0;
    86 }

转载于:https://www.cnblogs.com/blue-lin/p/10915194.html

[PAT A1142_Maximal Clique_25]: https://pintia.cn/problem-sets/994805342720868352/problems/994805343979159552
[https_en.wikipedia.org_wiki_Clique_graph_theory]: https://en.wikipedia.org/wiki/Clique_%28graph_theory
[Link 1]: https://www.cnblogs.com/blue-lin/p/10878108.html