PAT 图联通

峰会,判定首脑是否认识

满分

/**
题意: 朋友聚会
条件1:
所有朋友相互认识
2: 若还可以加朋友,需要再加
3: 若有相互不认识,则请求帮助


*/
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;
const int N = 210;
bool g[N][N];
int f , m, n, q;
bool is_friend(vector<int> &vc)
{
    for(int i = 0; i < vc.size() - 1; i++)
    {
        for(int j = i + 1; j < vc.size(); j++)
        {
            int a = vc[i], b = vc[j];
            if (!g[a][b]) return false;
        }
    }
    return true;
}
bool need_friend(vector<int> &vc)
{
    for(int i = 1; i <= m; i++)
    {
        int cnt = 0;
        for(auto &t: vc)
        {
            if (g[i][t]) cnt++;
        }
        if (cnt == vc.size()) {
            f = i;
            return true;
        }
    }
    return false;
}
int main()
{

    cin >> m >> n;
    while (n --)
    {
        int a, b;
        cin >> a >> b;
        g[a][b] = g[b][a] = true;
    }
    cin >> q;
    for(int i = 1; i <= q; i++)
    {
        int k;
        cin >> k;
        vector<int> vc(k);
        for(int j = 0; j < k; j++) cin >> vc[j];
        if (!is_friend(vc)) printf("Area %d needs help.\n", i);
        else
        {
            if (need_friend(vc)) printf("Area %d may invite more people, such as %d.\n", i, f);
            else printf("Area %d is OK.\n", i);
        }
    }
}

5分, 3个格式错误

方法二

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

const int N = 210;
bool g[N][N], visit[N];
int m, n, q;
void check(vector<int> &res)
{
    // 判断连通
    bool f1 = true;
    memset(visit, false, sizeof visit);
    for(int i = 0; i < res.size(); i++)
    {
        visit[res[i]] = true;
        for(int j = i + 1; j < res.size(); j++)
        {
            int x = res[i], y = res[j];
            if (!g[x][y]) f1 = false;
        }
    }
    if (!f1) puts("needs help.\n");
    else {

        for(int i = 1; i <= m; i++)
        {
            bool f2 = true;
            if (!visit[i])
            {
                for(int j = 0; j < res.size(); j++)
                {
                    if (!f2) break;
                    if (!g[i][res[j]]) f2 = false;
                }
                if (f2)
                {
                    printf("may invite more people, such as %d.\n", i);
                    return;
                }
            }

        }
        printf("is OK.\n");
    }
}
int main()
{
    cin >> m >> n;
    while (n --)
    {
        int a, b;
        cin >> a >> b;
        g[a][b] = g[b][a] = true;
    }
    cin >> q;
    int k;
    for(int j = 1; j <= q; j++)
    {
        cin >> k;
        vector<int> res(k);
        for(int i = 0; i < k; i++) cin >> res[i];
        printf("Area %d ", j);
        check(res);
    }
}

满分 第一次写的代码

方法一

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 210;
bool g[N][N], visit[N];
int m, n, k;
void check(vector<int> &res, int id)
{
    printf("Area %d ", id);
    bool flag = true, f1 = false;
    memset(visit, false, sizeof visit);
    for(int i = 0; i < res.size(); i++)
    {
        visit[res[i]] = true;
        // 这一步错了, 应该判断所有人中,是否都是朋友
        for(int j = i + 1; j < res.size(); j++)
        {
            if (!g[res[i]][res[j]])
            {
                flag = false;
            }
        }
    }
    // 这个一定要先本身连通, 再加朋友
    // 本身不是朋友,直接help
    if (flag)
    {
        for(int i = 1; i <= m; i++)
        {
            if (visit[i] == false)
            {
                int cnt = 0;
                // 判断本身是否连通
                for(int j = 0; j < res.size(); j++, cnt++)
                {
                    if (!g[i][res[j]]) break;
                }
                //
                if (cnt == res.size())
                {
                    f1 = true;
                    printf("may invite more people, such as %d.\n", i);
                    return;
                }
            }
        }
    }

    if (!f1 && !flag) printf("needs help.\n");
    else if (!f1) printf("is OK.\n");

}

int main()
{
    cin >> m >> n;
    while (n --)
    {
        int a, b;
        cin >> a >> b;
        g[a][b] = g[b][a] = true;
    }
    cin >> k;
    int n1;
    for(int i = 1; i <= k; i++)
    {
        cin >> n1;
        vector<int> res(n1);
        for(int j = 0; j < n1; j++) cin >> res[j];

        // 判断是否任意两者联通
        check(res, i);
    }
}