A1166峰会区域安排问题（25分）PAT甲级C++满分解析【图论】

在峰会上，峰会是指国家元首或政府首脑之间的会议。为了确保会议顺利进行，需要精心规划休息区的安排，使每个区域内的所有领导人都能相互认识且互为直接朋友。

给定一系列可能的休息区安排方案，您的任务是评估每个方案是否满足上述理想条件。

输入描述：

每个输入文件包含一个测试用例。每个用例的第一行给出两个正整数N (≤ 200)，表示参加峰会的领导人数量，以及M，表示友谊关系的数量。接下来的M行每行包含一对数字，表示两位相互友好的领导人的编号。领导人从1至N编号。

随后是一个正整数K (≤ 100)，表示有K种不同的休息区安排方案。接下来的K行每行首先给出一个正整数L (≤ N)，然后是L个不同的领导人编号，表示一个可能的休息区安排方案。同一行中的所有数字由空格分隔。

输出描述：

对于每个休息区，按照以下格式输出您的建议：

• 如果在这个区域内每个人都直接是其他人的朋友，并且没有遗漏的朋友（即没有其他人与这个区域内的所有人都直接友好），则输出Area X is OK.。


• 如果在这个区域内每个人都直接是其他人的朋友，但还有其他领导人也可以被邀请而不破坏理想的安排，则输出Area X may invite more people, such as H.，其中H是最小编号的可邀请领导人。


• 如果这个区域的安排不是理想的，则输出Area X needs help.，以便主办方可以提供特别服务帮助领导人相互了解。

这里的X是从1到K的区域索引。

示例输入：

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
2 4 6
3 3 2 1

示例输出：

Area 1 is OK.
Area 2 is OK.
Area 3 is OK.
Area 4 is OK.
Area 5 may invite more people, such as 3.
Area 6 needs help.

参考代码：

#include 
#include 
using namespace std;

vector> edge(250, vector(250, 0));

int main() {
    int n, m;
    cin >> n >> m; // n个节点m条边
    for (int i = 0; i         int x, y;
        cin >> x >> y;
        edge[x][y] = edge[y][x] = 1; // 建立图的连接
    }
    int k;
    cin >> k;
    for (int i = 1; i <= k; i++) {
        int l; // 每个area的点的个数
        cin >> l;
        vector v(l);
        for (int j = 0; j             cin >> v[j];
        bool flag1 = true;
        for (int j = 0; j             for (int k = j + 1; k                 if (edge[v[j]][v[k]] == 0) {
                    flag1 = false;
                    break;
                }
            }
            if (!flag1) break;
        }
        bool flag2 = false;
        int minn = -1;
        for (int j = 1; j <= n; j++) {
            int k;
            for (k = 0; k                 if (j == v[k]) break;
                if (j != v[k] && edge[j][v[k]] == 0) break;
            }
            if (k == l) {
                flag2 = true;
                minn = j;
                break;
            }
        }
        if (!flag1) printf("Area %d needs help.\n", i);
        else if (flag2) printf("Area %d may invite more people, such as %d.\n", i, minn);
        else printf("Area %d is OK.\n", i);
    }
    return 0;
}

运行结果：