1142 Maximal Clique

最新推荐文章于 2025-03-19 10:57:39 发布

sheepyWYY

最新推荐文章于 2025-03-19 10:57:39 发布

阅读量211

点赞数

本文链接：https://blog.csdn.net/sheepyWYY/article/details/87116817

版权

本文深入探讨了PAT竞赛中新题型的解题思路，特别聚焦于图论中的Clique问题。通过具体代码示例，分享了一种从单一节点构建完整Clique的有效算法，同时记录了在实现过程中遇到的挑战与优化思考。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

许久没有练习PAT了，是时候刷一刷新的PAT了。

感觉现在图的题换了风格。

这个题目的Clique的主要解法还是：从一个点开始构建整个Clique，每次添加一个点，如果这个点和已经在Clique集合里面的点都临界我们就把他加入到Clique集合里面来。

补充一下后面修改的时候遇到的问题。感觉这个题还是验证原序列之后再添加邻接点好一点。不然直接算可能性还是比较多可能性的。

我现在写的程序有点乱，感觉应该可以再优化一下，让程序更简洁。

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <string.h>

#define MAX 210

using namespace std;

int Nv, Ne;	//起点为1
int M;
bool isVisit[MAX];
vector<int> graph[MAX];



bool isInClique(set<int> & clique, int * list, int n) {
	for (int j = 1; j < n; j++) {
		memset(isVisit, 0, sizeof(isVisit));
		//标记邻接点
		for (int z = 0; z < graph[list[j]].size(); z++) {
			isVisit[graph[list[j]][z]] = true;
		}

		set<int> ::iterator it;
		for (it = clique.begin(); it != clique.end(); it++) {
			if (!isVisit[*it]) {
				return false;
			}
		}

		clique.insert(list[j]);
	}
	return true;
}

bool isInClique(set<int> & clique, int v) {
	bool isAdjcent[MAX] = { 0 };

	for (int i = 0; i < graph[v].size(); i++) {
		isAdjcent[graph[v][i]] = true;
	}

	set<int> ::iterator it;
	for (it = clique.begin(); it != clique.end(); it++) {
		if (!isAdjcent[*it]) {
			return false;
		}
	}

	clique.insert(v);
	return true;
}




int main() {
	scanf("%d %d", &Nv, &Ne);

	for (int i = 0; i < Ne; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	scanf("%d", &M);
	for (int i = 0; i < M; i++) {
		int n;
		scanf("%d", &n);
		int * list = new int[n];

		for (int j = 0; j < n; j++) {
			scanf("%d", &list[j]);
		}
		set <int> clique = { list[0] };
		bool isClique = isInClique(clique,list,n);
		
		if (!isClique) {
			printf("Not a Clique\n");
		}
		else {

			memset(isVisit, 0, sizeof(isVisit));
			set<int> ::iterator it;
			//标记已经访问过的点
			for (it = clique.begin(); it != clique.end(); it++) {
				isVisit[*it] = true;
			}

			//对clique里面的临界点进行加点，看能不能再加点
			for (it = clique.begin(); it != clique.end(); it++) {
				for (int i = 0; i < graph[*it].size(); i++) {
					int nextV = graph[*it][i];
					if (!isVisit[nextV]) {
						isVisit[nextV] = true;
						isInClique(clique, nextV);
					}
				}
			}

			if (clique.size() != n) {
				printf("Not Maximal\n");
			}
			else {
				printf("Yes\n");
			}
		}

	}

	return 0;


}