PAT_A1142#Maximal Clique
Source:
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))
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, printNot Maximal
; or if it is not a clique at all, printNot 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:
Attention:
- 想的有点多,数据规模不大,暴力求解就好了
Code:
/*
Data: 2019-08-06 20:50:04
Problem: PAT_A1142#Maximal Clique
AC: 30:25 题目大意:
判断所给子图是否是完全图(无向图)
输入:
第一行给出,顶点数Nv<=200,Ne边数
接下来Ne行,v1,v2
接下来一行,给出查询数M;
接下来M行,给出顶点数K,和K个顶点;
输出:
YES,最大完全子图;
Not Maximal,完全子图,非最大
Not a Clique,完全图 基本思路:
先判断所给子图是否是完全图,
再遍历图中其余顶点,加入该子图,判断是否为完全图
*/
#include<cstdio>
#include<algorithm>
using namespace std;
const int M=1e3,INF=1e9;
int grap[M][M],v[M],vis[M]; int main()
{
#ifdef ONLINE_JUDGE
#else
freopen("Test.txt", "r", stdin);
#endif // ONLINE_JUDGE int n,m,k,v1,v2;
scanf("%d%d", &n,&m);
fill(grap[],grap[]+M*M,INF);
for(int i=; i<m; i++)
{
scanf("%d%d", &v1,&v2);
grap[v1][v2]=;
grap[v2][v1]=;
}
scanf("%d", &m);
while(m--)
{
scanf("%d", &k);
fill(vis,vis+n+,);
for(int i=; i<k; i++)
{
scanf("%d", &v[i]);
vis[v[i]]=;
}
for(int i=; i<k-; i++)
{
v1 = v[i];
for(int j=i+; j<k; j++)
{
v2=v[j];
if(grap[v1][v2]==INF)
{
k=;
break;
}
v1=v2;
}
}
if(k==)
{
printf("Not a Clique\n");
continue;
}
for(int i=; i<=n; i++)
{
if(vis[i]==)
{
for(int j=; j<k; j++)
{
if(grap[i][v[j]]==INF)
{
vis[i]=;
break;
}
}
if(vis[i]==)
{
printf("Not Maximal\n");
k=;break;
}
}
}
if(k)
printf("Yes\n");
} return ;
}
最新文章
- Netty(五)序列化protobuf在netty中的使用
- 获取去除参数url地址
- AX 2012 在Grid 中添加image标识状态
- Java --ClassLoader创建、加载class、卸载class
- uml中的几种关系
- nginx模块开发(18)—日志分析
- Vuex源码解析
- 使用HttpClient4.5实现HTTPS的双向认证
- 多线程threading
- Java之IO流进阶篇:内存流,打印流,对象流
- 如何设置默认以管理员权限运行cmd
- 【翻译】Flume 1.8.0 User Guide(用户指南) source
- Caffe使用新版本CUDA和CuDNN
- oracle基础函数--decode
- 配置完centos 6以后,大概需要安装的软件(主要是yum)
- 修改linux swap空间的swappiness,降低对硬盘的缓存
- @Java虚拟机之对象访问
- WebForm中使用MVC
- angularJs的工具方法3
- krpano之语音介绍
热门文章
- [bzoj2086][Poi2010]Blocks_单调栈_双指针
- HDU 5239 上海大都会 D题(线段树+数论)
- HDU 4508
- 在imageView依次加入7个手势, 1.点击哪个button,往imageView上加入哪个手势.(保证视图上仅仅有一个手势). 2.轻拍:点击视图切换美女图片.(imageView上首先展示的美女
- 苹果的编程语言--Swift
- 修改android系统开机动画
- Android系统Recovery工作原理之使用update.zip升级过程分析(七)---Recovery服务的核心install_package函数【转】
- spring:按照Bean的名称自动装配User
- POJ 2728(最优比率生成树+01规划)
- Coursera Algorithms week1 查并集 练习测验:2 Union-find with specific canonical element