问题描述

我正在尝试解决在我的国家的一所大学的考试中提出的问题。它给了我一个包含在第一行 3 数字的文件作为输入：

第一个(n)代表人数

第二个（m）代表人与人之间的友谊数

第三个（k）是序列的大小（但序列不必和这个数字一样大，可以更大）

...在第二行，关系（m 对形式为 (a, b) 的数字表示 a 是 b 的朋友，b 是 a 的朋友）。

任务是尽可能有效地找到人们彼此成为朋友的最大长度（至少是 k 个人）的序列。如果没有这样的序列，将打印“NO”。

他们的例子：

数据.txt：

5 5 3
1 2 5 1 3 2 4 5 1 4

输出：

1 4 5

数据.txt：

5 5 4
1 2 5 1 3 2 4 5 1 4

输出：

No

数据.txt：

11 18 3 
1 8 4 7 7 10 11 10 2 1 2 3 8 9 8 3 9 3 9 2 5 6 5 11 1 4 10 6 7 6 2 8 11 7 11 6

输出.txt：

2 3 6 7 8 9 10 11

我的方法

在这种情况下，友谊可以用无向图表示（至少对我来说，这似乎是最合乎逻辑的数据结构），其中顶点代表人，边代表友谊。要成为序列的一部分，顶点的度数必须大于或等于 k - 1。

这就是我停下来的地方。目前我所能做的就是消除度数至少为 k - 1 的节点：

#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>

std::ifstream f{ "data.txt" };

constexpr size_t LIMIT = 101;

// graph[i][j]: i is friend with j
// short to avoid vector<bool> specialization
std::vector<std::vector<short>> graph(LIMIT, std::vector<short>(LIMIT, 0));
std::vector<int> validNodes;

int numOfNodes, numOfRelationships, sequenceSize;

void Read()
{
    f >> numOfNodes >> numOfRelationships >> sequenceSize;

    int a;
    int b;

    for(int i = 1; i <= numOfRelationships; ++i) {
        f >> a >> b;

        graph[a][b] = graph[b][a] = 1;
    }
}

int Degree(int node)
{
    int result = 0;

    for(int i = 1; i <= numOfNodes; ++i) {
        if(i != node && graph[node][i] == 1) {
            ++result;
        }
    } 

    return result;
}

void KeepValidNodes()
{
    for(int i = 1; i <= numOfNodes; ++i) {
        if(Degree(i) < sequenceSize - 1) {
            // Don't add the node to validNodes vector
            // "Remove it from the graph" aka it's not friend with anyone
            // all nodes that were friends with it now have a lower degree, remove them from the validNodes vector if that's the case
            for(int j = 1; j <= numOfNodes; ++j) {
                auto findPos = std::find(validNodes.begin(), validNodes.end(), j);

                if(findPos != validNodes.end() && Degree(j) - 1 < sequenceSize - 1) {
                    *findPos = -1;
                }

                graph[i][j] = graph[j][i] = 0;
            } 
        }
        else {
            validNodes.push_back(i);
        }
    } 
}

void PrintSequence()
{
    bool empty = true;

    for(const int& node : validNodes) {
        if(node != -1) {
            empty = false;
            std::cout << node << std::endl;
        }
    }

    if(empty) {
        std::cout << "No" << std::endl;
    }
}

int main()
{
    Read();
    KeepValidNodes();
    PrintSequence();
}

这仅适用于他们的前 2 个示例。我能想到的唯一可能的解决方案是生成所有可能的节点组合，看看哪个满足要求。正如他们所说，我怎样才能有效地解决这个问题？

编辑：

我不一定要寻找完整的工作代码，但我什至不知道如何解决这个问题。

标签： c++

c++ - 如何找到彼此为朋友的大小为 k（或更多）的人的序列？

问题描述

数据.txt：

输出：

数据.txt：

输出：

数据.txt：

输出.txt：

我的方法

编辑：

解决方案

推荐阅读