1142 Maximal Clique
2024-08-31 12:40:54
题意:给出一个图,定义这样一个结点子集subset,若subset中的任意两结点不都相邻,则称之为Not a Clique;若subset中的任意两结点都相邻,则称之为Clique;若subset中的结点不仅都相邻,而且不存在subset之外的点与subset中的每个结点都相邻,则称之为Maximal。
思路:首先,判断待查询的结点是否都相邻;其次,判断是不是Maximal。怎么判断呢?遍历所有subset之外的结点(可以用vis[]数组来表示,标记subset[]里的结点为true,这样就只会访问非subset的点了),只要存在这样一个结点v,使得v与subset中的每个结点都相邻,则说明subset不是Maximal。
代码:
#include <cstdio> #include <cstring> ; }; int subset[maxn];//存放每次检查的结点 int vis[maxn];//标记在集合中出现过的结点 int n,m; int main() { scanf("%d%d",&n,&m); int u,v; while(m--){ scanf("%d%d",&u,&v); graph[u][v]=graph[v][u]=; } int query,k; scanf("%d",&query); while(query--){ scanf("%d",&k); memset(vis,,sizeof(vis));//每次查询前记得初始化 ;i<k;i++){ scanf("%d",&subset[i]); vis[subset[i]]=; } ;//1->Yes; 0->Not Maximal; -1->Not a Clique //1.检验是不是Clique ;i<k;i++){ ) break; ;j<k;j++){ ) { flag=-; break; } } } ){ printf("Not a Clique\n"); continue; } //2.检验是不是Maximal ;v<=n;v++){ if(vis[v]) continue; vis[v]=; ; for(;i<k;i++) ) break; if(i==k){ flag=;//但凡存在一个不是subset中的结点使得该结点与subset中的每个结点都相连,说明它不是Maximal break; } }//for ) printf("Yes\n"); else printf("Not Maximal\n"); } ; }
最新文章
- linux 汇编
- android 画虚线、实线,画圆角矩形,一半圆角
- NSDate用法整理总结
- 关于scrollWidth,clientWidth,offsetWidth
- P2P的原理和常见的实现方式(为libjingle开路)
- DataTable.select() 返回 DataTable
- .NET SOCKET通信编程
- Android Support v4,v7,v13
- iOS开发 - NSBundle, NSDevice, NSLocale
- bzoj1433 [ZJOI2009]假期的宿舍(最大流)
- BZOJ 3196
- hdu3986Harry Potter and the Final Battle
- NPOI:创建Workbook和Sheet
- sizeof和strlen的使用
- 上海嘉韦思杯部分writeup
- hibernate框架学习之数据模型-POJO
- 20155326刘美岑 《网络对抗》Exp1 PC平台逆向破解
- BF算法和KMP算法 python实现
- python基础操作以及其常用内置方法
- django 一个关于分组查询的问题分析
热门文章
- python学习笔记(控制语句)
- spring3: 内置Resource实现
- Linux:安装Zookeeper
- 一般处理程序ashx中用session存储数据
- 使用swagger作为restful api的doc文档生成——从源码中去提取restful URL接口描述文档
- Mac os x 下配置Intellij IDEA + Tomcat 出现权限问题的解决办法
- 《Java程序员职场全攻略 从小工到专家》 - 书摘精要
- ADO.NET数据库访问技术(转)
- CSS3 Media Query 响应式媒体查询
- vsftpd的530 Login incorrect错误解决方法 vsftpd登录错误