关于算法-数据结构:PAT甲级2019年冬季考试-73-Summit

A summit (峰会) is a meeting of heads of state or government. Arranging the rest areas for the summit is not a simple job. The ideal arrangement of one area is to invite those heads so that everyone is a direct friend of everyone.

Now given a set of tentative arrangements, your job is to tell the organizers whether or not each area is all set.

Each input file contains one test case. For each case, the first line gives two positive integers N (≤ 200), the number of heads in the summit, and M, the number of friendship relations. Then M lines follow, each gives a pair of indices of the heads who are friends to each other. The heads are indexed from 1 to N.

Then there is another positive integer K (≤ 100), and K lines of tentative arrangement of rest areas follow, each first gives a positive number L (≤ N), then followed by a sequence of L distinct indices of the heads. All the numbers in a line are separated by a space.

For each of the K areas, print in a line your advice in the following format:

if in this area everyone is a direct friend of everyone, and no friend is missing (that is, no one else is a direct friend of everyone in this area), print Area X is OK..
if in this area everyone is a direct friend of everyone, yet there are some other heads who may also be invited without breaking the ideal arrangement, print Area X may invite more people, such as H. where H is the smallest index of the head who may be invited.
if in this area the arrangement is not an ideal one, then print Area X needs help. so the host can provide some special service to help the heads get to know each other.

Here X is the index of an area, starting from 1 to K.

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.

现给定一个 N 个顶点，M 条边的无向图，给出 K 个查问，每一个查问是一个顶点汇合，须要判断以后顶点联合是否是一个齐全子图，如果不是，输入 Area X needs help. 其中 X 为查问的编号，从 1 开始，否则判断是否存在一个顶点与该汇合中的所有顶点都边相连，如果有，输入 Area X may invite more people, such as H. 其中 H 为那个顶点。如果没有，输入 Area X is OK。

应用邻接矩阵 G 判断任意两点是否连通，arrange 存储每次查问的顶点汇合，isExist 标记查问的顶点汇合，每一次查问的时候，首先应用 isAllConnected 判断 arrange 中的每一个点是否都有边相连，如果是返回 true，否则返回 false，printf(“Area %d needs help.\n”,i);, 代码如下：

bool isAllConnected(){for(int i:arrange){for(int j:arrange){if(i!=j&&G[i][j]==0){return false;}
        }
    }
    return true;
}

而后再应用 getMorePeople 判断以后的顶点汇合是否能够再增加其他人退出，如果能够返回顶点编号，否则返回 -1，如果返回 -1，printf("Area %d is OK.\n",i); 否则 printf("Area %d may invite more people, such as %d.\n",i,a); (a 为返回值), 代码如下：

int getMorePeople(){for (int i = 1; i <= N; ++i) {
        // 判断以后人 i 是否能够增加到汇合 arrange 中
        bool possible = true;
        // i 在汇合 arrange 中了
        if(isExist[i]) continue;
        for(int j:arrange){if(G[i][j]==0){possible = false;}
        }
        if(possible){
            // i 退出汇合 arrange 中后与所有人都连通
            return i;
        }
    }
    return -1;
}

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<vector>

using namespace std;

int G[205][205];
vector<int> arrange;
int N,M;
bool isExist[205];

bool isAllConnected(){for(int i:arrange){for(int j:arrange){if(i!=j&&G[i][j]==0){return false;}
        }
    }
    return true;
}

int getMorePeople(){for (int i = 1; i <= N; ++i) {
        // 判断以后人 i 是否能够增加到汇合 arrange 中
        bool possible = true;
        // i 在汇合 arrange 中了
        if(isExist[i]) continue;
        for(int j:arrange){if(G[i][j]==0){possible = false;}
        }
        if(possible){
            // i 退出汇合 arrange 中后与所有人都连通
            return i;
        }
    }
    return -1;
}

int main(){scanf("%d %d",&N,&M);
    for (int i = 0; i < M; ++i) {
        int a,b;
        scanf("%d %d",&a,&b);
        G[a][b] = G[b][a] = 1;
    }
    int K;
    scanf("%d",&K);
    for(int i=1;i<=K;++i){
        int num;
        scanf("%d",&num);
        arrange.clear();
        memset(isExist,0, sizeof(isExist));
        for (int j = 0; j < num; ++j) {
            int a;
            scanf("%d",&a);
            arrange.push_back(a);
            isExist[a] = true;
        }
        // 判断是否齐全连通
        if(!isAllConnected()){
            // 不是齐全连通
            printf("Area %d needs help.\n",i);
        } else {int a = getMorePeople();
            if(a==-1){printf("Area %d is OK.\n",i);
            } else {printf("Area %d may invite more people, such as %d.\n",i,a);
            }
        }
    }
    return 0;
}

关于算法-数据结构:PAT甲级2019年冬季考试-73-Summit

7-3 Summit (25 分)

Input Specification:

Output Specification:

Sample Input:

Sample Output:

题目限度：

题目粗心：

算法思路：

提交后果：

AC 代码：