主页 / 问题 / 669182
Accepted
VVK
Asked:2020-05-22 18:39:26 +0000 UTC2020-05-22 18:39:26 +0000 UTC

图构建，对排序问题

  • 772

下午好，请帮我优化解决问题。有一组数字对 [a, b]，例如

[0, 1], [3, 2], [4, 0], [3, 4], [2, 1], [9, 8], [10, 9], [8, 10]

这个集合有 n 个不同长度的循环“链”，在每一对中，元素 a 和 b 可以是任何顺序。

实际上任务是建立这些链：

[0, 1], [1, 2], [2, 3], [3, 4], [4, 0] и [8, 9], [9, 10], [10, 8]

最有可能的是，该算法包括构建一个图，其中数字是顶点，对是边。

我将不胜感激任何帮助或建议。

алгоритм

1 个回答

  1. Best Answer

    考虑到评论中的答案，任务变得极其简单。C++ 中的解决方案。

    int main() {
    map < int ,pair<int,int>> back;
    map <int, bool> used;
    int a,b;
    while (cin >>a >> b){
        if (!back.count(a))
            back[a] = make_pair(b,0);
        else back[a] = make_pair( back[a].first,  b);

        if (!back.count(b))
            back[b] = make_pair(a,0);
        else back[b] = make_pair( back[b].first,  a);       
    }

    for (auto x : back){
        auto R = x.first;   

        while (!used[R]){
            used[R] = true;
            cout << R<<" ";
            if (!used[back[R].first])
                R = back[R].first;
            else R = back[R].second;
        }
        cout << endl;
    }

    return 0;
}

    顺便说一下，您错过了条件中的边 [3,4]。运行示例

    这个想法很简单——我们在每个组件中只有一个循环，我们只需要仔细检查它。

    • 1

相关问题