pat 訓練題 7-5 基友團 (25分) 暴力判團和最大團

基友，是指男性之間關系親密的朋友。對于新一代的年輕人來說，基友也常常用在生活步調在一個節奏，或者相處好的同性身上，是以就有了新一代話語：“好基友，一輩子”“好基友，一生一起走”等說法。每逢周末，約上幾個好友，喝喝小酒，吃吃雞，男人的快樂就這麼簡單。現在有一個問題，一個妹子想統計男朋友的基友團有多大，需要你幫助。 什麼叫基友團呢？就是圈子裡的男人兩兩之間都是好基友。

輸入格式:

第一行輸入兩個數，N，M，N表示總共有多少個男人，N<200，從1号開始編号，M表示總共有多個兩兩之間的好基友關系。 接下來的M行，每一行給出兩個數字，表示這兩個之間存在好基友關系。 接下來輸入一個數T，表示要判斷多少行， T < 100 接下來的T行，按以下方式輸入：

K ID1 ID2 …… IDK

K表示基友圈裡有多少個人，後面K個資料分别是基友圈裡人的編号。

輸出格式:

對T組查詢，在一行中輸出判斷結論。如果是最大基友團（不包含在任何一個基友團之内的基友團），輸出Yes，如果是基友團，但是不是最大，那麼輸出Not Maximal，如果根本不是基友團，那麼輸出Not a Clique

輸入樣例:

在這裡給出一組輸入。例如：

4 4

1 2

1 3

2 3

2 4

3

2 4 1

3 1 3 2

2 2 3

輸出樣例:

在這裡給出相應的輸出。例如：

Not a Clique

Yes

Not Maximal

題目：給定一個圖，和一些詢問，每次詢問

K

個點，如果是

團

且不被包含在其他團内輸出

Yes

，

是

團

且被包含則

Not Max

，否則輸出``no`

1. 資料小，直接暴力即可
2. 先判斷詢問點是否兩兩相連

   O(n^2)

3. 如果兩兩相連，則嘗試找到一個

   其他點S

   ，滿足

   S

   與所有詢問點有邊

   O(n)

   1. 找到，不是最大

   2. 找不到，最大

input
3 1
1 2
3
2 1 2
1 1
1 3
output
Yes
Not Maximal
Yes
           

input
4 5
1 2
2 3
3 4
3 1
1 4
4
3 1 2 3
2 1 3
4 1 2 3 4
1 4
output
Yes
Not Maximal
Not a Clique
Not Maximal
           

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
output
Yes
Yes
Yes
Yes
Not Maximal
Not a Clique
           

input
3 0
2
1 1
2 2 3
output
Yes
Not a Clique
           

c++

// #define debug
#ifdef debug
#include <time.h>
#include "win_majiao.h"
#endif

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

#define MAXN ((int)1e5+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;
typedef vector<vector<int> > VVI;

#define show(x...) \
	do { \
		cout << "\033[31;1m " << #x << " -> "; \
		err(x); \
	} while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

namespace FastIO{

	char print_f[105];
	void read() {}
	void print() { putchar('\n'); }

	template <typename T, typename... T2>
	   inline void read(T &x, T2 &... oth) {
		   x = 0;
		   char ch = getchar();
		   ll f = 1;
		   while (!isdigit(ch)) {
			   if (ch == '-') f *= -1; 
			   ch = getchar();
		   }
		   while (isdigit(ch)) {
			   x = x * 10 + ch - 48;
			   ch = getchar();
		   }
		   x *= f;
		   read(oth...);
	   }
	template <typename T, typename... T2>
	   inline void print(T x, T2... oth) {
		   ll p3=-1;
		   if(x<0) putchar('-'), x=-x;
		   do{
				print_f[++p3] = x%10 + 48;
		   } while(x/=10);
		   while(p3>=0) putchar(print_f[p3--]);
		   putchar(' ');
		   print(oth...);
	   }
} // namespace FastIO
using FastIO::print;
using FastIO::read;

int n, m, Q, K;
int G[256][256];
bool findit(vector<int>& arr) { //嘗試找到一個點，該點和詢問點都有邊
	bool vis[256] = { 0 };
	for(auto x : arr) vis[x] = true;
	for(int i=1; i<=n; i++) {
		if(vis[i]) continue ;
		int u = i;
		bool ok = true;
		for(auto v : arr) {
			if(!G[u][v] || !G[v][u]) ok = false;
		}
		if(ok) return true;
	}
	return false;
}

signed main() {
#ifdef debug
	freopen("test.txt", "r", stdin);
	clock_t stime = clock();
#endif
	read(n, m);
	int u, v;
	for(int i=1; i<=m; i++) {
		read(u, v);
		G[u][v] = G[v][u] = true;
	}

	read(Q);
	while(Q --) {
		read(K);
		vector<int> arr;
		while(K--) { 
			read(m);
			arr.push_back(m);
		}
		bool p2p = true;
		for(int i=0; i<arr.size(); i++) { //暴力判斷詢問點是否兩兩有邊
			// printf("%d : ", arr[i]);
			for(int j=0; j<i; j++) {
				u = arr[i], v = arr[j];
				// printf("(%d %d) ", arr[j], G[u][v]);
				p2p = p2p && (G[u][v] && G[v][u]);
			}
			// printf("\n");
		}
		if(!p2p) {
			printf("Not a Clique\n");
			continue ;
		} else {
			bool fit = findit(arr); //嘗試找到與詢問點都有邊的點
			if(fit) printf("Not Maximal\n");
			else printf("Yes\n");
		}
		
	}





#ifdef debug
	clock_t etime = clock();
	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
	return 0;
}