PAT甲级1142 Maximal Clique ：[C++题解]图论、最大团、枚举

文章目录

• • 题目分析
  • 题目链接

题目分析

来源：acwing

分析：

团：团是顶点的集合，满足该集合中任意两顶点之间都有边。

判断是不是团：所有点是否有边
判断最大团：是否可以加一个额外点，使得所有点之间都有边。

数据较小，直接O(n^2)暴力可以过。

开邻接矩阵标志存在边。判断团：二重循环遍历给定的点，判断是否存在边。

判断最大团：二重循环遍历添加进来新的点，看看新点是否和集合内的点都两两存在边，如果存在没有边的情况，就不是最大团。

AC代码

#include<bits/stdc++.h> using namespace std; const int N =300;int n, m; bool g[N][N],st[N]; int ver[N];bool check_clique(int cnt){for(int i =0; i< cnt ;i++)for(int j =0; j<i ;j++)//没有边if(!g[ver[i]][ver[j]]) return false;return true; }bool check_maximum(int cnt){memset(st, 0 ,sizeof st);//集合内的点做好标记for(int i =0; i< cnt; i++)st[ver[i]] =true;//遍历集合外的点for(int i =1; i<= n; i++){if(!st[i]){bool success = true;//遍历集合内的点：看是否存在边for(int j = 0; j< cnt; j++){if(!g[i][ver[j]]){success =false;break;}}if(success) return false; //不是最大团}}return true; } int main(){cin >> n >> m;while(m--){int a, b;cin >> a >> b;g[a][b] =g[b][a] =true;}int k;cin >> k;while(k--){int cnt;cin >> cnt;//读入顶点for(int i = 0; i<cnt; i++) cin >> ver[i]; if(check_clique(cnt)) {if(check_maximum(cnt)) cout<<"Yes"<<endl;else cout<<"Not Maximal"<<endl;}else cout<<"Not a Clique"<<endl;} }

题目链接

PAT甲级1142 Maximal Clique
https://www.acwing.com/problem/content/1637/

总结

以上是生活随笔为你收集整理的PAT甲级1142 Maximal Clique ：[C++题解]图论、最大团、枚举的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。