1142 Maximal Clique (25 分) 判断最大团

小灰灰 2024-04-17 05:36 152阅读 0赞

1142 Maximal Clique (25 分)

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

**题意：**给定n个结点，m条双向边。k个询问，每个询问m个数字，问是否构成最大团。

若是最大团则输出yes，若为团却非最大则输出not maximal，不是最大团则not a clique。

团的定义：团中每个结点都直接相连，直接判a\[i\]\[j\]即可，不用跑prime。

#include <stdio.h>
    #include <string.h>
    #include <string>
    #include <map>
    #include <vector>
    #include <queue>
    #include <math.h>
    #include <algorithm>
    #include <iostream>
    #define INF 0x3f3f3f3f
    using namespace std;
    int a[205][205];
    int main()
    {
    	int n,m,k,i,j,x,y;
    	memset(a,0,sizeof a);
    	scanf("%d%d",&n,&m);
    	for(i=0;i<m;i++)
    	{
    		scanf("%d%d",&x,&y);
    		a[x][y]=a[y][x]=1;
    	}
    	scanf("%d",&k);
    	while(k--)
    	{
    		scanf("%d",&m);
    		int x[1005];
    		for(i=0;i<m;i++)
    		scanf("%d",&x[i]);
    		int flag=0;
    		for(i=0;i<m;i++)
    		{
    			for(j=0;j<m;j++)
    			{
    				if(i==j)continue;
    				if(a[x[i]][x[j]]!=1)
    				{
    					flag=1;
    					break;
    				}
    			}
    		}
    		if(flag) printf("Not a Clique\n");
    		else
    		{
    			int cnt=0;
    			for(i=1;i<=n;i++)
    			{
    				int f=1;
    				for(j=0;j<m;j++)
    				{
    					if(i!=x[j]&&!a[i][x[j]])
    						f=0;
    				}
    				if(f)cnt++;
    			}
    			if(cnt==m)
    			printf("Yes\n");
    			else 
    			printf("Not Maximal\n");
    		}
    	}
    }

[https_en.wikipedia.org_wiki_Clique_graph_theory]: https://en.wikipedia.org/wiki/Clique_%28graph_theory