题目链接:
题目简述:这个题目还是依旧给个图。在题目中给了一个名为clique
的定义,即:它为所给图所有节点的子集,且在这个集合中的节点两两邻接。如果再加入其它的节点还满足两两相连,那么这个clique
就是Not Maximal
,否则就是Yes
。
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> graph(201, vector<int>(201, 0));
vector<int> adj[201], temp(201);
void getAns(int k){
for (int i = 0; i < k;i++){
for (int j = i + 1; j < k;j++){
if(graph[temp[i]][temp[j]] == 0){
cout << "Not a Clique" << endl;
return;
}
}
}
for (int i = 0; i < k;i++){
for (int j = 0; j < adj[temp[i]].size();j++){
int h = 0;
for (; h < k;h++){
if(h == i) continue;
if(graph[temp[h]][adj[temp[i]][j]] == 0)
break;
}
if(h == k){
cout << "Not Maximal" << endl;
return;
}
}
}
cout << "Yes" << endl;
return;
}
int main(){
int N, E, M, K;
int c1, c2;
cin >> N >> E;
for (int i = 0; i < E;i++){
cin >> c1 >> c2;
graph[c1][c2] = graph[c2][c1] = 1;
adj[c1].push_back(c2);
adj[c2].push_back(c1);
}
cin >> M;
while(M--){
cin >> K;
for (int i = 0; i < K;i++)
cin >> temp[i];
getAns(K);
}
return 0;
}
就是先按平常的先把图存起来,然后再去判断。这边判断就是纯暴力了,直接一遍撸过去,不过得先判是不是团,再判是不是不是最大团,最后再输出最大团。return的逻辑还是很好用的。
因篇幅问题不能全部显示,请点此查看更多更全内容
Copyright © 2019- sceh.cn 版权所有 湘ICP备2023017654号-4
违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务